题解 P4879 【ycz的妹子】
Juan_feng
2018-10-09 09:10:10
## 这么好的一道分块题怎么能没有分块的题解呢QAQ
小蒟蒻就不多废话了，直接进入正题:
对于Q，C，I，D这四种操作
**Q操作**就是一个简单的区间求和，维护一个ans数组就可以了
**C操作**直接修改就行了（别忘了维护ans数组）
**D操作**可能稍微麻烦一点，动态删点这种东西一看就烦人呀qwq，所以小蒟蒻图个省事就直接吧所有的可能会出现的点都加进去了，删除的时候只要把要删的那个点的数值清零，再下个标记就好了
那么有dalao可能要问了，你个蒟蒻**怎么找到第x个妹子**呀？其实这也好办，维护一个geshu数组保存每个块内的妹子的数量，和妹子分手（删点）的时候就把这个点所在的块的**geshu--** 这样找第x个妹子的时候就可以从头开始找，一次加上一个块的妹子数量，直到找到答案所在的块，然后再暴力去找就可以了。
这样**I操作**也不难了，如果这个点有妹子的话就直接修改，维护ans，反之如果这个点现在没有妹子，那么让这个点所在块的**geshu++**就好了。
你看小蒟蒻辣么菜，也没多少时间去细想，就没怎么去优化，想必各位dalao一定可以想出更优秀的分块做法呀qwq
**（要是有什么更好的分块想法或者有对小蒟蒻程序的优化和建议还请一定要私信我呀qwq）**
那么代码如下：
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
#define FOR(i,l,r) for(re ll i=l;i<=r;++i)
#define maxn 200010
#define ll long long
using namespace std;
ll n,m,r,t,x,y,z,sq,now;
ll a[maxn],b[maxn],c[maxn],tag[maxn],bl[maxn],geshu[maxn],ans[maxn];
char ch;
inline void in(ll &x){ //无处不在的快读
x=0;ll f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c==-1) return;
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x=x*f;
}
inline void out(ll a){
if(a<0){
a*=-1;
putchar('-');
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}
ll query(ll x,ll y){ //区间求和
ll res=0;
FOR(i,x,min(y,b[x]*sq))
res+=a[i];
if(b[x]!=b[y])
FOR(i,(b[y]-1)*sq+1,y)
res+=a[i];
FOR(i,b[x]+1,b[y]-1)
res+=ans[i]+sq*tag[i];
return res;
}
ll sss(ll x){ //已知妹子序号找该妹子所在的城市
ll res=0;
ll rt=1;
while(res+geshu[rt]<x){
res+=geshu[rt];
++rt;
}
FOR(i,(rt-1)*sq+1,min(n,rt*sq)){
if(bl[i]==0){
++res;
}
if(res==x){
return i;
}
}
return 0;
}
int main(){
in(now),in(m);
n=200001;
sq=sqrt(n);
FOR(i,1,n){ //预处理
b[i]=(i-1)/sq+1;
if(i>now)
bl[i]=1;
}
FOR(i,1,now){
in(a[i]),geshu[b[i]]++,ans[b[i]]+=a[i];
}
FOR(i,1,m){
cin>>ch;
if(ch=='Q'){
out(query(1,now)); //一点毛病没有的求和
puts("");
}
if(ch=='C'){ //无懈可击的修改
in(x),in(y);
if(!bl[x]){ //bl为0代表有妹子
a[x]-=y;
ans[b[x]]-=y;
}
}
if(ch=='D'){
in(x);
ll cs=sss(x); // 第x个妹子所在的城市
ans[b[cs]]-=a[cs];
a[cs]=0;
bl[cs]=1; //标记这个城市没有妹子了
--geshu[b[cs]];
}
if(ch=='I'){
in(x),in(y);
ans[b[x]]-=a[x];
a[x]=y;
ans[b[x]]+=a[x];
if(bl[x]==1){//如果这个城市没有妹子
++geshu[b[x]];
bl[x]=0;
}
if(x>now)
now=x;
}
}
return 0;//功德圆满。
}
```
**最后祝大家NOIP RP++！**