唉突然回忆起去年去noipnoipnoip提高组试水然后省二滚粗的悲惨经历。。。
往事不堪回首。
所以说考场上真的有debuffdebuffdebuff啊!!!虽然当时我也不会权值线段树
这道题直接上权值线段树维护nnn行和第mmm列就行了。
原因?
这是因为每次修改只会影响到某一行和最后一列。
但直接跑是会炸空间的。
因此我们动态开点来操作一波就行了。
对于被删除的点我们存到vectorvectorvector里面就行。
代码:
#include<bits/stdc++.h>using namespace std;inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}typedef long long ll;const int N=600005;vector<ll>g[N];int siz[N*50],rt[N],son[N*50][2],n,m,q,tot=0;ll lim;inline void update(int&p,int l,int r,int k){if(!p)p=++tot;++siz[p];if(l==r)return;int mid=l+r>>1;if(k<=mid)update(son[p][0],l,mid,k);else update(son[p][1],mid+1,r,k);}inline int query(int p,int l,int r,int k){if(l==r)return l;int mid=l+r>>1,sum=mid-l+1-siz[son[p][0]];if(sum>=k)return query(son[p][0],l,mid,k);return query(son[p][1],mid+1,r,k-sum);}inline ll modifr(int x,ll v){int k=query(rt[n+1],1,lim,x);update(rt[n+1],1,lim,k);ll ret=k<=n?(ll)k*m:g[n+1][k-n-1];return g[n+1].push_back(v?v:ret),ret;}inline ll modifl(int px,int py){int k=query(rt[px],1,lim,py);update(rt[px],1,lim,k);ll ret=k<m?(ll)(px-1)*m+k:g[px][k-m];return g[px].push_back(modifr(px,ret)),ret;}int main(){n=read(),m=read(),q=read(),lim=max(n,m)+q;for(int i=1,x,y;i<=q;++i)x=read(),y=read(),printf("%lld\n",(y==m)?modifr(x,0):modifl(x,y));return 0;}