4170: 極光
Time Limit:?30 Sec??Memory Limit:?512 MB
Submit:?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 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 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<y.a; 26 return (x.b==y.b)?(x.c<y.c):(x.b<y.b); 27 } 28 bool cmp2(int x,int y) {return (t[x].b==t[y].b)?(t[x].c<t[y].c):(t[x].b<t[y].b);} 29 30 int cc[Maxm*10],nw[Maxm*10]; 31 void ad(int x,int y) {for(int i=x;i<=q+1;i+=i&(-i)) cc[i]+=y;} 32 int query(int x) {int as=0;for(int i=x;i>=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 else 77 { 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<len;i++) printf("%d %d %d %d %d %d\n",t[i].a,t[i].b,t[i].c,t[i].id,t[i].f,t[i].ans); 87 for(int i=1;i<=ans[0];i++) printf("%d\n",ans[i]); 88 return 0; 89 }
認真地開了數組大小很久還是RE，干脆全部乘10了。。。
?
2017-03-26?16:40:39
