CodeForces 85D Sum of Medians Splay

题解：

对于这个题目，先想到是建立5棵Splay，然后每次更新把后面一段区间的树切下来，然后再转圈圈把切下来的树和别的树合并。

但是感觉写起来太麻烦就放弃了。

建立5棵线段树。

然后 seg[rt][i]代表的是只考虑当前所管辖的区间中的情况下，下标对5取余之后为 i 的那些值的和。

最重要的一点是更新。

for(int i = ; i < ; ++i)

        seg[i][rt] = seg[i][rt<<] + seg[((i-sz[rt<<]%)+)%][rt<<|];

我们可以通过左边的sz，来找到右边的数如果加上前面的sz之后，第i个值是哪里过来的。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

int sz[N<<];

LL seg[][N<<];

int op[N], v[N];

int b[N], m;

char s[N];

int id(int x){

    return lower_bound(b+, b++m, x) - b;

}

void Updata(int L, int v, int l, int r, int rt){

    if(l == r){

        seg[][rt] += b[L] * v;

        sz[rt] += v;

        return ;

    }

    int m = l+r >> ;

    if(L <= m) Updata(L, v, lson);

    else Updata(L, v, rson);

    sz[rt] += v;

    for(int i = ; i < ; ++i)

        seg[i][rt] = seg[i][rt<<] + seg[((i-sz[rt<<]%)+)%][rt<<|];

}

int main(){

    int q;

    scanf("%d", &q);

    for(int i = ; i <= q; ++i){

        scanf("%s", s);

        if(s[] == 'a') {

            op[i] = ;

            scanf("%d", &v[i]);

            b[++m] = v[i];

        }

        else if(s[] == 'd'){

            op[i] = -;

            scanf("%d", &v[i]);

        }

    }

    sort(b+, b++m);

    m = unique(b+, b++m) - (b+);

    for(int i = ; i <= q; ++i){

        if(!op[i]) printf("%lld\n", seg[][]);

        else

            Updata(id(v[i]), op[i], , m, );

    }

    return ;

}

/*

4

add 1

add 2

add 3

sum

*/

巴特西

CodeForces 85D Sum of Medians Splay | 线段树

最新文章

热门文章