Description

給定一個長度為n的正整數數列a[i]。 定義2個位置的graze值為兩者位置差與數值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。 2種操作（k都是正整數）： 1.Modify x k：將第x個數的值修改為k。 2.Query x k：詢問有幾個i滿足graze(x,i)<=k。因為可持久化數據結構的流行，詢問不僅要考慮當前數列，還要考慮任意歷史版本，即統計任意位置上出現過的任意數值與當前的a[x]的graze值<=k的對數。（某位置多次修改為同樣的數值，按多次統計）

Input

第1行兩個整數n,q。分別表示數列長度和操作數。 第2行n個正整數，代表初始數列。 第3--q+2行每行一個操作。

Output

????對于每次詢問操作，輸出一個非負整數表示答案。

Sample Input

3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

Sample Output

2
3
3

HINT

N<=60000?修改操作數<=40000?詢問<=10000?Max{a[i]}含修改<=100000

思路：考場上打了個暴力，竟然有70分....

CDQ分治，先把坐標（x,y）轉換成(x-y,x+y)，然后就是正放著的矩形了，詢問就是矩形中點的個數。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=60010,maxm=260010,maxq=500010; int n,q,a[maxn],ans[maxq],cnt,lim; bool que[maxq];char op[10]; struct node{int num,id,op,x,y,t;}li[maxq],tmp[maxq]; struct Bit{int val[maxq]; void change(int x,int v){for (;x<=lim;x+=x&-x) val[x]+=v;}int query(int x){int res=0;for (;x;x-=x&-x) res+=val[x];return res;} }T;void add(int op,int id,int x,int y,int k){int xx=x-y,yy=x+y;if (!op) lim=max(lim,xx),lim=max(lim,yy),li[++cnt]=(node){cnt,id,op,xx,yy,0};else{int x1=xx-k,y1=yy-k,x2=xx+k,y2=yy+k;if (y1>0) li[++cnt]=(node){cnt,id,op,x1-1,y1-1,1};li[++cnt]=(node){cnt,id,op,x1-1,y2,-1};if (y1>0) li[++cnt]=(node){cnt,id,op,x2,y1-1,-1};li[++cnt]=(node){cnt,id,op,x2,y2,1};lim=max(lim,x2),lim=max(lim,y2);} }void solve(int l,int r){if (l==r) return;int mid=(l+r)>>1;solve(l,mid),solve(mid+1,r);for (int i=l,a=l,b=mid+1;i<=r;i++){node p;if (a<=mid&&(b>r||li[a].x<=li[b].x)) p=li[a++];else p=li[b++];if (p.num<=mid&&!p.op) T.change(p.y,1);if (p.num>mid&&p.op) ans[p.id]+=T.query(p.y)*p.t;tmp[i]=p;}for (int i=l;i<=r;i++) li[i]=tmp[i];for (int i=l;i<=r;i++) if (li[i].num<=mid&&!li[i].op) T.change(li[i].y,-1); }int main(){scanf("%d%d",&n,&q);for (int i=1;i<=n;i++) scanf("%d",&a[i]),add(0,i,i,a[i],0);for (int i=n+1,x,k;i<=n+q;i++){scanf("%s%d%d",op,&x,&k);if (op[0]=='M') a[x]=k,add(0,i,x,a[x],0);else que[i]=1,add(1,i,x,a[x],k);}n+=q,lim++,solve(1,cnt);for (int i=1;i<=cnt;i++) if (que[i]) printf("%d\n",ans[i]);return 0; }

轉載于:https://www.cnblogs.com/thythy/p/5493585.html

總結

以上是生活随笔為你收集整理的bzoj29894170: 数列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。