樹狀數組+二分--NOIP2017 D2T3 列隊

傳送門

一開始隻會 50 50 50分暴力，把詢問離線然後模拟就行

正解是線段樹 o r or or樹狀數組 o r or or平衡樹

樹狀數組常數小而且好寫就寫了這個

首先一個詢問隻和目前詢問以及之前對 x x x行的詢問有關，可以離線詢問，然後預處理出 p r e [ i ] pre[i] pre[i]表示第 i i i個詢問應該是第 x x x行的第幾個，這個可以用樹狀數組 + + +二分

拿樹狀數組和一個 v e c t o r vector vector維護最後一列，再用 n n n個 v e c t o r vector vector維護每一行，從前往後周遊詢問，首先算出目前 x x x行的末尾 h h h是第幾個數，然後把它删掉，

如果 h ≤ n h\le n h≤n，則 a n s = h × m ans=h\times m ans=h×m

否則， a n s = n u m [ 0 ] [ h − n − 1 ] ans=num[0][h-n-1] ans=num[0][h−n−1]（下标從 0 0 0開始）

若詢問的 y = m y=m y=m，此時 a n s ans ans就是答案

如果不是，就在第 x x x的 v e c t o r vector vector末尾添上 a n s ans ans，然後看 p r e [ i ] pre[i] pre[i]

如果 p r e [ i ] &lt; m pre[i]&lt;m pre[i]<m， a n s = ( x − 1 ) × m + p r e [ i ] ans=(x-1)\times m+pre[i] ans=(x−1)×m+pre[i]

否則 a n s = n u m [ x ] [ p r e [ i ] − m ] ans=num[x][pre[i]-m] ans=num[x][pre[i]−m]

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<vector>
#define N 300001
#define LL long long
using namespace std;
int mx,n,m,q,f[N<<1],qu[N][2],pre[N];

inline int rd(){
	static int x,f;static char c; x=0,f=1,c=' ';
	while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();
	while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();
	return x*f; 
}

struct qwq{
	int pos,id;
	qwq(){}
	qwq(int x,int y){pos=x,id=y;}
};
vector<qwq> vec[N];
vector<LL> num[N];

inline void add(int x,int y){
	for(;x<=mx;x+=x&-x) f[x]+=y;
}
inline int ask(int x){
	int sum=0;
	for(;x;x-=x&-x) sum+=f[x];
	return sum;
}

inline int query(int k){
	int l=0,r=mx,mid,res;
	while(l<=r){
		mid=l+r>>1;
		if(ask(mid)>=k) res=mid,r=mid-1;
		else l=mid+1;
	} return res;
}

inline void prework(){
	for(int i=1;i<=mx;i++) add(i,1);
	qwq now;
	for(int i=1;i<=n;i++){
		for(int j=0;j<vec[i].size();j++){
			now=vec[i][j];
			pre[now.id]=query(now.pos);
			add(pre[now.id],-1);
		}
		for(int j=0;j<vec[i].size();j++)
			add(pre[vec[i][j].id],1);
	}
		
}

inline void solve(){
	prework(); LL ans;int h;
	for(int i=1;i<=q;i++){
		h=query(qu[i][0]); add(h,-1);
		if(h<=n) ans=1LL*h*m;
		else ans=num[0][h-n-1];
		if(qu[i][1]!=m){
			num[qu[i][0]].push_back(ans);
			if(pre[i]<m) ans=1LL*(qu[i][0]-1)*m+pre[i];
			else ans=num[qu[i][0]][pre[i]-m];
		}
		num[0].push_back(ans);
		printf("%lld\n",ans);
	}
}

int main(){
	n=rd(); m=rd(); q=rd();
	mx=max(m,n)+q;
	for(int i=1;i<=q;i++){
		qu[i][0]=rd(), qu[i][1]=rd();
		if(qu[i][1]!=m) 
			vec[qu[i][0]].push_back(qwq(qu[i][1],i));
	}
	solve();
	return 0;
}