# 求助TLE50

@I_am_a_SB 2019-03-26 19:59 回复

# include<algorithm>

using namespace std;

# define ll long long int

int n,m,q; int root[300005]; ll size[1200005]; ll l[1200005],r[1200005]; int lc[1200005],rc[1200005]; int cnt,x,y;

void newnode(int rt,ll k,int &p) { ++cnt; rc[cnt]=rc[rt]; lc[cnt]=rc[rt]=0; r[cnt]=r[rt]; r[rt]=l[rt]+k-1; l[cnt]=r[rt]+1; size[cnt]=size[rc[cnt]]+r[cnt]-l[cnt]+1; size[rt]=size[lc[rt]]+r[rt]-l[rt]+1; p=cnt; return; }

int merge(int a,int b) { if(a==0||b==0) return a+b; if(rand()&1){ rc[a]=merge(rc[a],b); size[a]=size[lc[a]]+size[rc[a]]+r[a]-l[a]+1; return a; } else{ lc[b]=merge(a,lc[b]); size[b]=size[lc[b]]+size[rc[b]]+r[b]-l[b]+1; return b; } }

void split(int rt,int k,int &a,int &b) { if(rt==0){ a=b=0; return; } if(size[lc[rt]]>=k){ b=rt; split(lc[rt],k,a,lc[b]); size[b]=size[lc[b]]+size[rc[b]]+r[b]-l[b]+1; } else if(size[lc[rt]]+r[rt]-l[rt]+1<=k){ a=rt; split(rc[rt],k-size[lc[rt]]-r[rt]+l[rt]-1,rc[a],b); size[a]=size[lc[a]]+size[rc[a]]+r[a]-l[a]+1; } else{ newnode(rt,k-size[lc[rt]],b); a=rt; } return; }

int main(void) { srand(871372874); scanf("%d%d%d",&n,&m,&q); root[0]=size[0]=0; cnt=2n; for(int i=1;i<=n;i++){ l[i]=(ll)(i-1)m+1; r[i]=(ll)im-1; root[i]=i; size[i]=m-1; size[i+n]=1; l[i+n]=r[i+n]=(ll)im; lc[i]=rc[i]=lc[i+n]=rc[i+n]=0; root[0]=merge(root[0],i+n); }

while(q--){
int a,b,c,d,e,f;
scanf("%d%d",&x,&y);
if(y==m){
split(root[0],x-1,a,b);
split(b,1,b,c);
//  printf("%lld\n",l[b]);
root[0]=merge((merge(a,c)),b);
}
else{
split(root[x],y-1,a,b);
split(b,1,b,c);
//  printf("%lld\n",l[b]);
split(root[0],x-1,d,e);
split(e,1,e,f);
root[x]=merge(merge(a,c),e);
root[0]=merge(merge(d,f),b);
}
}
return 0;

}

@I_am_a_SB 2019-03-26 20:00 回复 举报
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define ll long long int

int n,m,q;
int root[300005];
ll size[1200005];
ll l[1200005],r[1200005];
int lc[1200005],rc[1200005];
int cnt,x,y;

void newnode(int rt,ll k,int &p)
{
++cnt;
rc[cnt]=rc[rt];
lc[cnt]=rc[rt]=0;
r[cnt]=r[rt];
r[rt]=l[rt]+k-1;
l[cnt]=r[rt]+1;
size[cnt]=size[rc[cnt]]+r[cnt]-l[cnt]+1;
size[rt]=size[lc[rt]]+r[rt]-l[rt]+1;
p=cnt;
return;
}

int merge(int a,int b)
{
if(a==0||b==0)
return a+b;
if(rand()&1){
rc[a]=merge(rc[a],b);
size[a]=size[lc[a]]+size[rc[a]]+r[a]-l[a]+1;
return a;
}
else{
lc[b]=merge(a,lc[b]);
size[b]=size[lc[b]]+size[rc[b]]+r[b]-l[b]+1;
return b;
}
}

void split(int rt,int k,int &a,int &b)
{
if(rt==0){
a=b=0;
return;
}
if(size[lc[rt]]>=k){
b=rt;
split(lc[rt],k,a,lc[b]);
size[b]=size[lc[b]]+size[rc[b]]+r[b]-l[b]+1;
}
else if(size[lc[rt]]+r[rt]-l[rt]+1<=k){
a=rt;
split(rc[rt],k-size[lc[rt]]-r[rt]+l[rt]-1,rc[a],b);
size[a]=size[lc[a]]+size[rc[a]]+r[a]-l[a]+1;
}
else{
newnode(rt,k-size[lc[rt]],b);
a=rt;
}
return;
}

int main(void)
{freopen("testdata.in","r",stdin);
srand(871372874);
scanf("%d%d%d",&n,&m,&q);
root[0]=size[0]=0;
cnt=2*n;
for(int i=1;i<=n;i++){
l[i]=(ll)(i-1)*m+1;
r[i]=(ll)i*m-1;
root[i]=i;
size[i]=m-1; size[i+n]=1;
l[i+n]=r[i+n]=(ll)i*m;
lc[i]=rc[i]=lc[i+n]=rc[i+n]=0;
root[0]=merge(root[0],i+n);
}

while(q--){
int a,b,c,d,e,f;
scanf("%d%d",&x,&y);
if(y==m){
split(root[0],x-1,a,b);
split(b,1,b,c);
//  printf("%lld\n",l[b]);
root[0]=merge((merge(a,c)),b);
}
else{
split(root[x],y-1,a,b);
split(b,1,b,c);
//  printf("%lld\n",l[b]);
split(root[0],x-1,d,e);
split(e,1,e,f);
root[x]=merge(merge(a,c),e);
root[0]=merge(merge(d,f),b);
}
}
return 0;
}