求助TLE50

回复帖子

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

代码:(#11本机5s)

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) { 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;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。