BZOJ 2989: 数列 & 4170: 极光 January 8, 2017 ###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 询问<=60000 Max{a[i]}含修改<=100000 ###Solution 这道题其实是维护两种操作，向平面上加点，查询菱形内点数 把(x,y)变为(x+y,x-y)，菱形就变成了正方形 假设某个询问是以(x0,y0)为中心，边长为2k的正方形，那么可以拆成两个，一个是x>=x0-k且x<=x0+k且y<=y0+k的点数，另一个是x>=x0-k且x<=x0+k且y<y0-k的点数，把两个询问做差就和原询问相同 那么可以CDQ分治，按y排序，x用树状数组维护 ###Code ```c++ #include<bits/stdc++.h> using namespace std; int n,m,s[60001],ans[60000],ac,qc,mx; struct query { int x,y,k,id;char op; }q[230000],tmp[230000]; inline void add(int x,int y){q[qc].x=x+y,q[qc].y=x-y,qc++,mx=max(mx,x+y);} int p[160001]; inline void pl(int x){for(;x<=mx;x+=x&-x)p[x]++;} inline int qr(int x){if(x<=0)return 0;int r=0;for(x=min(x,mx);x;x^=x&-x)r+=p[x];return r;} inline void cl(int x){for(;x<=mx;x+=x&-x)p[x]=0;} void work(int l,int r) { if(l==r)return; int mid=(l+r)>>1; work(l,mid),work(mid+1,r); int i1=l,i2=mid+1,ti=l; for(;i2<=r;tmp[ti++]=q[i2++]) { for(;i1<=mid&&q[i1].y<=q[i2].y;tmp[ti++]=q[i1++]) if(!q[i1].op)pl(q[i1].x); if(q[i2].op) { if(q[i2].op==1) ans[q[i2].id]+=qr(q[i2].x+q[i2].k)-qr(q[i2].x-q[i2].k-1); else ans[q[i2].id]+=qr(q[i2].x-q[i2].k-1)-qr(q[i2].x+q[i2].k); } } for(;i1<=mid;tmp[ti++]=q[i1++]); for(i1=l;i1<=mid;i1++)if(!q[i1].op)cl(q[i1].x); for(i1=l;i1<=r;i1++)q[i1]=tmp[i1]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",s+i),add(i,s[i]); char tmp[10];int a,b; while(m--) { scanf("%s%d%d",tmp,&a,&b); if(tmp[0]=='M') add(a,s[a]=b); else { int x=a+s[a],y=a-s[a]; q[qc].x=x,q[qc].y=y+b,q[qc].k=b,q[qc].id=ac,q[qc].op=1,qc++; q[qc].x=x,q[qc].y=y-b-1,q[qc].k=b,q[qc].id=ac,q[qc].op=2,qc++; ac++; } } work(0,qc-1); for(int i=0;i<ac;i++) printf("%d\n",ans[i]); } ```
BZOJ 4722: 由乃 November 27, 2016 ###Description 给一个长为n的序列a，每个数在0到v - 1之间，有m次操作。 操作1：每次询问一个区间中是否可以选出两个下标的集合X，Y，满足： 1.X和Y没有交集 2.设集合X中有一个元素是i，则其对集合X的贡献是a[i] + 1，要求集合X的元素的总贡献和集合Y的元素的总贡献 相等如果可以选出这两个集合，输出 Yuno否则输出 Yuki 操作2：修改一个区间l,r之间的数，使得所有l <= i <= r，a[i] = a[i] \* a[i] \* a[i] % v ，即区间立方 ###Input 第一行三个数n , m , v，意义如题所述 之后一行n个数，表示序列a 之后m行每行三个数opt , l , r，表示操作类型是1还是2，操作的区间是[l , r] ###Output m行，每行一个字符串 Yuno 或者 Yuki 表示能否选出这两个集合 ###Sample Input 20 20 152 3 26 133 54 79 81 72 109 66 91 82 100 35 23 104 17 51 114 12 58 2 1 17 2 6 12 1 1 12 2 3 5 2 11 11 2 7 19 2 6 15 1 5 12 1 1 9 1 10 19 2 3 19 2 6 20 2 1 13 2 1 15 2 1 9 1 1 1 2 1 7 2 7 19 2 6 19 2 3 6 ###Sample Output Yuno Yuno Yuno Yuno Yuki ###HINT 总算在bzoj上出题了呀 这下可以安心退役了~ 总共有10组数据 对于100%的数据，n , m <= 100000 , v <= 1000,数据没有梯度 ###Solution 当某个区间长度大于13一定有解，小于13 bitset乱搞 立方操作树状数组区间加，取数时倍增 ###Code ```c++ #include<bits/stdc++.h> int n,m,v,u,s[100001],p[100001],N[1000][17],i,j,O,l,r,t,T; main() { scanf("%d%d%d",&n,&m,&v); while((1<<u)<=v)u++; for(;i<v;i++) N[i][0]=1ll*i*i*i%v; for(i=1;i<=n;i++) scanf("%d",s+i); for(i=0;i<16;i++) for(j=0;j<v;j++) N[j][i+1]=N[N[j][i]][i]; while(m--) { scanf("%d%d%d",&O,&l,&r); if(O&1) { if(r-l>=u)puts("Yuno"); else { std::bitset<10360> x(1); for(i=l;i<=r;i++) { t=0,T=s[i]; for(j=i;j;j^=j&-j)t+=p[j]; for(j=0;j<17;j++)if((t>>j)&1)T=N[T][j]; if((x&(x<<T+1)).any()) { puts("Yuno"); goto Y; } x|=x<<T+1; } puts("Yuki"); Y:; } } else { for(i=l;i<=n;i+=i&-i)p[i]++; for(i=r+1;i<=n;i+=i&-i)p[i]--; } } } ```
BZOJ 3196: Tyvj 1730 二逼平衡树 November 17, 2016 ###Description 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x，且最大的数) 5.查询k在区间内的后继(后继定义为大于x，且最小的数) ###Input 第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数，表示有序序列 下面有m行，opt表示操作标号 若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名 若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数 若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k 若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱 若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继 ###Output 对于操作1,2,4,5各输出一行，表示查询结果 ###Sample Input 9 6 4 2 2 1 9 4 0 1 1 2 1 4 3 3 4 10 2 1 4 3 1 2 5 9 4 3 9 5 5 2 8 5 ###Sample Output 2 4 3 4 9 ###HINT 1.n和m的数据范围：n,m<=50000 2.序列中每个数的数据范围：[0,1e8] 3.虽然原题没有，但事实上5操作的k可能为负数 ###Solution 外层树状数组，内层值域线段树，在每个节点记count,修改时分别修改，查询时用r和l-1对应的一大堆节点做差（有点像主席树） ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) struct node { node *lc,*rc; int cnt; node(); }_null,*null=&_null; node::node(){lc=rc=null;cnt=0;} int pf; void erase(node *x) { if(x->lc!=null)erase(x->lc); if(x->rc!=null)erase(x->rc); delete x; } void modify(node *&x,int l,int r,int p,int v) { if(x==null)x=new node; x->cnt+=v; if(!x->cnt) { erase(x); x=null; return; } if(l!=r) { int f=(l+r)/2; if(p<=f) modify(x->lc,l,f,p,v); else modify(x->rc,f+1,r,p,v); } } struct group { node *x[50]; int mul[50],sz; inline int cnt() { int ret=0; for(int i=0;i<sz;i++)ret+=x[i]->cnt*mul[i]; return ret; } inline group* lc(group *f) { f->sz=sz; for(int i=0;i<sz;i++)f->x[i]=x[i]->lc,f->mul[i]=mul[i]; return f; } inline group* rc(group *f) { f->sz=sz; for(int i=0;i<sz;i++)f->x[i]=x[i]->rc,f->mul[i]=mul[i]; return f; } }; int cnt(group *x,int l,int r,int ql,int qr) { if(l==ql&&r==qr)return x->cnt(); int t=(l+r)/2,ans=0; group ch; if(ql<=t)ans+=cnt(x->lc(&ch),l,t,ql,min(t,qr)); if(qr>t)ans+=cnt(x->rc(&ch),t+1,r,max(ql,t+1),qr); return ans; } int kth(group *x,int l,int r,int rk) { if(l==r)return l; group ch; x->lc(&ch); int lcnt; if((lcnt=ch.cnt())>=rk) return kth(&ch,l,(l+r)/2,rk); else return kth(x->rc(&ch),(l+r)/2+1,r,rk-lcnt); } int gmax(group *x,int l,int r,int p) { if(!x->cnt())return 0; if(l==r)return l; int t=(l+r)/2; group ch; if(p<=t)return gmax(x->lc(&ch),l,t,p); if(r==p) { x->rc(&ch); if(ch.cnt())return gmax(&ch,t+1,r,p); return gmax(x->lc(&ch),l,t,t); } return max(gmax(x->lc(&ch),l,t,t),gmax(x->rc(&ch),t+1,r,p)); } int gmin(group *x,int l,int r,int p) { if(!x->cnt())return 0x7fffffff; if(l==r)return l; int t=(l+r)/2; group ch; if(p>t)return gmin(x->rc(&ch),t+1,r,p); if(l==p) { x->lc(&ch); if(ch.cnt())return gmin(&ch,l,t,p); return gmin(x->rc(&ch),t+1,r,t+1); } return min(gmin(x->lc(&ch),l,t,p),gmin(x->rc(&ch),t+1,r,t+1)); } #define nl 0 #define nr 100000001 node *root[50001]; int v[50001]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) root[i]=new node; for(int i=1;i<=n;i++) { scanf("%d",v+i); for(int j=i;j<=n;j+=lb(j)) modify(root[j],nl,nr,v[i],1); } while(m--) { int opt,a,b,c; scanf("%d%d%d",&opt,&a,&b); if(opt==3) { for(int j=a;j<=n;j+=lb(j)) modify(root[j],nl,nr,v[a],-1); v[a]=b; for(int j=a;j<=n;j+=lb(j)) modify(root[j],nl,nr,v[a],1); } else { scanf("%d",&c); group tmp; tmp.sz=0; for(int j=b;j;j^=lb(j)) tmp.mul[tmp.sz]=1,tmp.x[tmp.sz++]=root[j]; for(int j=a-1;j;j^=lb(j)) tmp.mul[tmp.sz]=-1,tmp.x[tmp.sz++]=root[j]; if(opt==1) { printf("%d\n",cnt(&tmp,nl,nr,nl,min(nr,c-1))+1); } else if(opt==2) { printf("%d\n",kth(&tmp,nl,nr,c)); } else if(opt==4) { printf("%d\n",gmax(&tmp,nl,nr,min(nr,c-1))); } else { printf("%d\n",gmin(&tmp,nl,nr,max(nl,c+1))); } } } } ```