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行描述每条指令，每行的格式是下面两种格式中的一种。 ( t{Q i j k}) 或者 ( t{C i t})
- ( t{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)小的数。
- $ t{C i t} $ ((1≤i≤n，0≤t≤10^9))表示把(a[i])改变成为(t)。
输出格式：
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
说明
(10\%)的数据中，(m,nle 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
",ans[i]);
return 0;
}
2018.10.31