频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
codeforces85D:Sum of Medians
2016-10-25 09:24:48         来源:qzh_1430586275的博客  
收藏   我要投稿

1、题意:维护一个集合,支持三种操作,向集合内添加或删除元素元素和查询里面排名取余5等于3的数的和,操作数n≤105元素的值≤109
2、分析:讲个笑话,这个题用vector纯模拟可以AC。
当然这么水的题发题解没啥意义。。来讨论另外一种做法。
一看见什么鬼畜排名当然想到线段树和平衡树之类的。这题可以用平衡树做。但是麻烦,那么我们离线,将元素的值离散化,建出来一个权值线段树来,那么一个区间里面存储什么呢?考虑既然是取余5等于3的话,我们可以将这个区间的数按照取余5的余数分类。这样就很好搞了,合并的话,就是把两个区间连起来,排名往后串一串就好了。询问就更简单了。如果这个题是区间查询操作的话,线段树也可以,在线操作的话,上treap。总之这个题的时间复杂度O(nlogn),可以优雅的通过

#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define M 400010
#define LL long long
#define VI vector
#define inf 2147483647
#define MOD 1000000007
#define rep(i, x, y) for(int i = (x); i <= (y); i ++)
#define drep(i, x, y) for(int i = (x); i >= (y); i --)

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

namespace segment_tree{
    struct Node{
        LL a[5]; int sum;

        inline void print(){
            rep(i, 0, 4) printf("%I64d ", a[i]);
            printf("%d \n", sum);
        }
    } q[M];
    int root;

    inline void update(int o, int y){
        if(y > 0) q[o] = (Node){y, 0, 0, 0, 0, 1};
        else q[o] = (Node){0, 0, 0, 0, 0, 0};
    }

    inline void pushup(int o){
        int l = q[2 * o].sum;
        rep(i, 0, 4) q[o].a[i] = q[2 * o].a[i] + q[2 * o + 1].a[((i - l) % 5 + 5) % 5];
        q[o].sum = q[2 * o].sum + q[2 * o + 1].sum;
    }

    inline void add(int l, int r, int o, int x, int y){
        if(l == r){
            update(o, y);
            return;
        }
        int mid = (l + r) / 2;
        if(x <= mid) add(l, mid, 2 * o, x, y);
        else add(mid + 1, r, 2 * o + 1, x, y);
        pushup(o);
    }


}

struct ops{
    int op, x, y;
} a[M];
pair b[M];
int cnt;
int len;

int main(){
    using namespace segment_tree; root = 1;
    int n = read(); char op[10];
    rep(i, 1, n){
        scanf("%s", op);
        if(op[0] == 'a'){
            int x = read();
            a[i] = (ops){1, x, 0};
            b[++ cnt] = make_pair(x, i);
        }
        else if(op[0] == 'd'){
            int x = read();
            a[i] = (ops){2, x, 0};
            b[++ cnt] = make_pair(x, i);
        }
        else{
            a[i] = (ops){3, 0, 0};
        }
    }
    sort(b + 1, b + cnt + 1);
    rep(i, 1, cnt){
        if(b[i].first != b[i - 1].first) len ++;
        a[b[i].second].y = len;
    }
    /*rep(i, 1, n){
        printf("%d %d %d\n", a[i].op, a[i].x, a[i].y);
    }*/
    rep(i, 1, n){
        if(a[i].op == 1){
            add(1, len, 1, a[i].y, a[i].x);
        }
        else if(a[i].op == 2){
            add(1, len, 1, a[i].y, -a[i].x);
        }
        else{
            printf("%I64d\n", q[1].a[2]);
        //  q[1].print();
        }
    }
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:Log4j、Log4j2、logback、slf4j日志学习
下一篇:SPOJ GSS 1~8
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站