P2617 Dynamic Rankings
题目描述
给定一个含有\(n\)个数的序列\(a[1],a[2],a[3],\dots,a[n]\)，程序必须回答这样的询问：对于给定的\(i,j,k\)，在\(a[i],a[i+1],a[i+2],\dots,a[j]\)中第\(k\)小的数是多少\((1≤k≤j-i+1)\)，并且，你可以改变一些\(a[i]\)的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列\(a\)，然后读入一系列的指令，包括询问指令和修改指令。
对于每一个询问指令，你必须输出正确的回答。
输入输出格式
输入格式：
第一行有两个正整数\(n,m\)。分别表示序列的长度和指令的个数
第二行有\(n\)个数，表示\(a[1],a[2],\dots,a[n]\)，这些数都小于\(10^9\)。接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。 \(\tt{Q \ i \ j \ k}\) 或者 \(\tt{C \ i \ t}\)
- \(\tt{Q\ i\ j\ k}\) （\(i,j,k\)是数字，\(1≤i≤j≤n, 1≤k≤j-i+1\)）表示询问指令，询问\(a[i],a[i+1],\dots,a[j]\)中第\(k\)小的数。
- $\tt{C\ i\ t} $ \((1≤i≤n，0≤t≤10^9)\)表示把\(a[i]\)改变成为\(t\)。
输出格式：
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
说明
\(10\%\)的数据中，\(m,n\le 100\);
\(20\%\)的数据中，\(m,n≤1000\);
\(50\%\)的数据中，\(m,n≤10000\)。
对于所有数据，\(m,n≤100000\)
整体二分即可。
因为刚学，有一点想了一会儿，如何保证操作的顺序？按原顺序读进来就可以了。
常数真小啊
Code:
#include <cstdio>
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N=300010;
const int inf=0x3f3f3f3f;
struct node{int op,x,y,k;}q[N],ql[N],qr[N];//类型,值,位置,1 or -1
int n,m,Q,s[N],a[N],ans[N];
void add(int x,int d){while(x<=n)s[x]+=d,x+=x&-x;}
int query(int x){int sum=0;while(x)sum+=s[x],x-=x&-x;return sum;}
void divide(int l,int r,int s,int t)
{
if(s>t) return;
if(l==r){rep(i,s,t)ans[q[i].op]=l;return;}
int lp=0,rp=0,mid=l+r>>1;
rep(i,s,t)
{
if(q[i].op)
{
int c=query(q[i].y)-query(q[i].x-1);
if(c>=q[i].k) ql[++lp]=q[i];
else qr[++rp]=q[i],qr[rp].k-=c;
}
else
{
if(q[i].x<=mid) add(q[i].y,q[i].k),ql[++lp]=q[i];
else qr[++rp]=q[i];
}
}
rep(i,s,t)
if(!q[i].op&&q[i].x<=mid) add(q[i].y,-q[i].k);
rep(i,s,s+lp-1) q[i]=ql[i+1-s];
rep(i,s+lp,t) q[i]=qr[i+1-s-lp];
divide(l,mid,s,s+lp-1),divide(mid+1,r,s+lp,t);
}
int main()
{
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%d",&q[i].x),q[i].y=i,q[i].k=1,a[i]=q[i].x;
rep(i,1,m)
{
int x,y,k;char op[3];
scanf("%s",op);
if(op[0]=='Q')
{
scanf("%d%d%d",&x,&y,&k);
q[++n]={++Q,x,y,k};
}
else
{
scanf("%d%d",&x,&y);
q[++n]={0,a[x],x,-1};
q[++n]={0,a[x]=y,x,1};
}
}
divide(-inf,inf,1,n);
rep(i,1,Q) printf("%d\n",ans[i]);
return 0;
}
2018.10.31