题解 P4879 【ycz的妹子】

· · 题解

大吼一声：

遇事不决先分块

然后就狗在机子前一下午； 这道题，充分证明读题的重要性；

如果你仅仅以为这是一道单点修改，那么你就GG了；

首先，分析一下题面：

1，ycz的妹子(青梅竹马)起初在1—n号城市中；但是，由于ycz的魅力强大，序列后面的妹子也会冒出来，所以，干脆直接把范围定位5e5(广撒网，多捞鱼) 雾~ 。 咳咳，是题面保证的；

2，题面说会有负值，那么颜值为0的也会有咯；所以不要把权值作为有或无的标志，再开个数组存一下；

3，对于编号为C的修改，直接修改，注意把快内和顺带改一下；

4，对于编号为I的修改，因为一城不容二女(难道城市只有两室一厅那么大 雾 )，后来的会顶走前面的，也就是覆盖；所以对于这个修改，要分此城市之前有无妹子，有就直接覆盖，顺带改下快内和，而之前没有，那么块中的妹子个数要加加，并且此城市别打上标记；

5，丢与编号为D的修改，应为找的是第X个有妹子的，所以，我们就有已经维护好的块内妹子个数来跳，找到对应的块，修改如上，只是赋0而已；

6，询问就是块的和，简单一加就行

7，最后的提醒，要开long long，不然~呃呃，你知道的；

最后，奉上我的代码，不懂有注释：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 1000500
using namespace std;

int n,m;
long long a[N],cnt[N],siz[N];//妹子的颜值，是否有妹子，块内妹子数
int L[N],R[N],tag[N]; //分块的编号，左右端点；
long long sum[N];//妹子和
int len,opt;//撒网范围

//修改1，简单修改
inline void Change_C(int x,int y) {
    if(!cnt[x]) return ;
    sum[tag[x]] -= a[x];
    a[x] -= y;
    sum[tag[x]] += a[x];
}

//修改2，分类讨论一下，顺带维护
inline void Change_I(int x,int y) {
    if(cnt[x]) {
        sum[tag[x]] -= a[x];
        a[x] = y;
        sum[tag[x]] += a[x];
    }
    else {
        cnt[x] = 1;
        sum[tag[x]] -= a[x];
        a[x] = y;
        sum[tag[x]] += a[x];
        siz[tag[x]] += 1;
    }
}

//跳妹子，找块并修改
inline void Change_D(int x) {
    int teg = 1;
    while(x - siz[teg] > 0) x -= siz[teg],teg ++;
    for(int i = L[teg];i <= R[teg];i ++) {
        if(x - cnt[i] == 0){
            siz[teg] --;
            sum[teg] -= a[i];
            cnt[i] = a[i] = 0;
            //别忘赋0
            return ;
        }
        else x -= cnt[i];
    } 
}

inline long long Qurry() {
    long long res = 0;
    for(int i = 1;i <= tag[opt];i ++)
        res += sum[i];
    return res;
}

int main() {
    opt = 500000;//广撒网
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]),cnt[i] = 1;
        //青梅竹马是喜欢ycz的，直接赋1
    len = sqrt(opt);
    for(int i = 1;i <= opt;i ++) 
        tag[i] = (i - 1) / len + 1;
    for(int i = 1;i <= tag[opt];i ++)
        L[i] = R[i - 1] + 1,R[i] = min(L[i] + len - 1,opt);
        //处理左右端点
    for(int i = 1;i <= tag[opt];i ++)
        for(int j = L[i];j <= R[i];j ++)
            sum[i] += a[j],siz[i] += cnt[j];
     //分块预处理

    for(int i = 1;i <= m;i ++) {
        char s[3]; int x,y; 
        scanf("%s",s + 1);
        if(s[1] == 'C') {
            scanf("%d%d",&x,&y);
            Change_C(x,y);
        }
        if(s[1] == 'I') {
            scanf("%d%d",&x,&y);
            Change_I(x,y);
        }
        if(s[1] == 'D') {
            scanf("%d",&x);
            Change_D(x);
        }
        if(s[1] == 'Q') 
            printf("%lld\n",Qurry());
    }
    return 0;
}

希望可以帮到大家； 喜欢分块————> 点我

Update

之前代码有锅，已修改，给大家带来不便请谅解QAQ