4170: 极光
Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 121 Solved: 64Description
"若是万一琪露诺(俗称rhl)进行攻击,什么都好,冷静地回答她的问题来吸引她。对方表现出兴趣的话,那就慢慢地反问。在她考虑答案的时候,趁机逃吧。就算是很简单的问题,她一定也答不上来。"--《上古之魔书》天空中出现了许多的北极光,这些北极光组成了一个长度为n的正整数数列a[i],远古之魔书上记载到:2个位置的graze值为两者位置差与数值差的和:graze(x,y)=|x-y|+|a[x]-a[y]|。要想破解天罚,就必须支持2种操作(k都是正整数):Modify x k:将第x个数的值修改为k。Query x k:询问有几个i满足graze(x,i)<=k。由于从前的天罚被圣王lmc破解了,所以rhl改进了她的法术,询问不仅要考虑当前数列,还要考虑任意历史版本,即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。(某位置多次修改为同样的数值,按多次统计)Input
第1行两个整数n,q。分别表示数列长度和操作数。第2行n个正整数,代表初始数列。第3~q+2行每行一个操作。N<=40000, 修改操作数<=40000, 询问操作数<=10000, Max{a[i]}(含修改)<=80000Output
对于每次询问操作,输出一个非负整数表示答案
Sample Input
3 5 2 4 3 Query 2 2 Modify 1 3 Query 2 2 Modify 1 2 Query 1 1Sample Output
2 3 3HINT
Source
【分析】
那个公式是曼哈顿距离的形式,把编号看成x,数值看成y,那就是在二维平面上不断给你一些点,然后问你距离某个点曼哈顿距离小于等于k的有多少个。
曼哈顿距离画出来是一个菱形区域,把它旋转,即(x,y)->(x-y,x+y),就是一个矩形区域,根据容斥分成4段求前缀。
那么加一个时间维就是一个经典的CDQ模型啦,三维偏序嘛~
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define Maxn 40010 8 #define Maxm 50010 9 10 struct node { int a,b,c,id,f,ans;}t[Maxn*10];11 int len=0;12 int ans[Maxm*10],w[Maxn*10];13 char s[10];14 int n,q;15 16 void add(int a,int b,int c,int id,int f)17 {18 // printf("%d %d %d %d %d\n",a,b,c,id,f);19 t[++len].a=a;t[len].b=b;t[len].c=c;t[len].id=id;t[len].f=f;20 t[len].ans=0;21 }22 23 bool cmp(node x,node y) 24 {25 if(x.a!=y.a) return x.a =1;i-=i&(-i)) as+=cc[i];return as;}33 34 void ffind(int l,int r)35 {36 if(l==r) return;37 int mid=(l+r)>>1;38 nw[0]=0;for(int i=l;i<=r;i++) nw[++nw[0]]=i;39 sort(nw+1,nw+1+nw[0],cmp2);40 for(int i=1;i<=nw[0];i++)41 {42 if(nw[i]<=mid&&t[nw[i]].id==0)43 {44 ad(t[nw[i]].c,1);45 }46 else if(nw[i]>mid&&t[nw[i]].id!=0)47 {48 t[nw[i]].ans+=query(t[nw[i]].c);49 }50 }51 for(int i=l;i<=r;i++) if(i<=mid&&t[i].id==0) ad(t[i].c,-1);52 ffind(l,mid);ffind(mid+1,r);53 }54 55 int main()56 {57 scanf("%d%d",&n,&q);58 memset(ans,0,sizeof(ans));59 for(int i=1;i<=n;i++)60 {61 int x;scanf("%d",&x);62 w[i]=x;63 add(i-x,i+x,1,0,0);64 }ans[0]=0;65 for(int i=1;i<=q;i++)66 {67 int x,y;68 scanf("%s%d%d",s,&x,&y);69 if(s[0]=='Q')70 {71 add(x-w[x]+y,x+w[x]+y,i+1,++ans[0],1);72 add(x-w[x]-y-1,x+w[x]-y-1,i+1,ans[0],1);73 add(x-w[x]-y-1,x+w[x]+y,i+1,ans[0],-1);74 add(x-w[x]+y,x+w[x]-y-1,i+1,ans[0],-1);75 }76 else77 {78 add(x-y,x+y,i+1,0,0);79 w[x]=y;80 }81 }82 sort(t+1,t+1+len,cmp);83 ffind(1,len);84 for(int i=1;i<=ans[0];i++) ans[i]=0;85 for(int i=1;i<=len;i++) if(t[i].id!=0) ans[t[i].id]+=t[i].f*t[i].ans;86 // for(int i=1;i
认真地开了数组大小很久还是RE,干脆全部乘10了。。。
2017-03-26 16:40:39