BZOJ1125: [POI2008]Poc

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 1e9+9
using namespace std;

inline void read(int &x)
{
    char c; while(!((c=getchar())>='0'&&c<='9'));
    x=c-'0';
    while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0';
}
inline int _max(int a,int b){return a>b?a:b;}
inline int _min(int a,int b){return ainline void up(int &x,const int &y){if(xinline void down(int &x,const int &y){if(x>y)x=y;}
const int maxn = 1100;
const int maxp = 210000;
const int maxl = 110;
const int mod = 1e9+7;
inline void add(int &a,const int b){a+=b; if(a>=mod) a-=mod;}

int n,m,l;
int root;
int ans[maxn],s[maxp];
int fa[maxp],son[maxp][2],siz[maxp],num[maxp],mx[maxp],mn[maxp],fl[maxn];
void pushup(const int x)
{
    int lc=son[x][0],rc=son[x][1];
    siz[x]=num[x]+siz[lc]+siz[rc];
    mx[x]=mn[x]=s[x];
    if(lc) up(mx[x],mx[lc]),down(mn[x],mn[lc]);
    if(rc) up(mx[x],mx[rc]),down(mn[x],mn[rc]);
}
void pushdown(const int x)
{
    if(fl[x])
    {
        int lc=son[x][0],rc=son[x][1]; up(ans[x],fl[x]);
        if(lc) up(fl[lc],fl[x]);
        if(rc) up(fl[rc],fl[x]);
        fl[x]=0;
    }
}
void rotate(int x,int &k)
{
    int y=fa[x],z=fa[y];
    if(y==k) k=x;
    else son[z][son[z][1]==y]=x;
    fa[x]=z;
    int l=son[y][1]==x,r=!l;
    son[y][l]=son[x][r],fa[son[x][r]]=y;
    son[x][r]=y,fa[y]=x;
    pushup(y);
}
int t[maxn],tp;
void splay(int x,int &k)
{
    int tmp=x; while(tmp) t[++tp]=tmp,tmp=fa[tmp];
    while(tp) pushdown(t[tp--]);
    for(int y=fa[x],z=fa[y];x!=k;rotate(x,k),y=fa[x],z=fa[y]) if(y!=k)
    {
        if((son[z][1]==y)^(son[y][1]==x)) rotate(x,k);
        else rotate(y,k);
    }pushup(x);
}
int fpre(const int k)
{
    for(int x=root;;)
    {
        if(s[x]int rc=son[x][1];
            if(!rc||mn[rc]>=k) return x;
            x=rc;
        }
        else x=son[x][0];
    }
}
int fsuf(const int k)
{
    for(int x=root;;)
    {
        if(kint lc=son[x][0];
            if(!lc||mx[lc]<=k) return x;
            x=lc;
        }
        else x=son[x][1];
    }
}
int go(int x,int d)
{
    while(son[x][d]) x=son[x][d];
    return x;
}
int gpre(int x)
{
    if(son[x][0]) return go(son[x][0],1);
    int y=fa[x],l=son[y][1]==x;
    while(!l)
        x=y,y=fa[x],l=son[y][1]==x;
    return y;
}
int gsuf(int x)
{
    if(son[x][1]) return go(son[x][1],0);
    int y=fa[x],l=son[y][1]==x;
    while(l)
        x=y,y=fa[x],l=son[y][1]==x;
    return y;
}
void erase(const int x)
{
    splay(x,root);
    splay(son[x][0],root);
    int y=fa[x],l=son[y][1]==x;
    int pre=gpre(x),suf=gsuf(x);
    splay(pre,root); splay(suf,son[root][1]);
    son[suf][0]=0; splay(suf,root);
}
void ins(const int x)
{
    mn[x]=mx[x]=s[x]; num[x]=1; siz[x]=0; fl[x]=0;
    int pre=fpre(s[x]),suf=fsuf(s[x]);
    splay(pre,root); splay(suf,son[root][1]);
    int &y=son[suf][0],z;
    if(!y) y=x,fa[x]=suf;
    else z=go(y,1),son[z][1]=x,fa[x]=z;
    fl[y]=siz[y]+1; splay(x,root);
}
char str[maxl];
int st[maxn][maxl];
int pw[maxl];

int main()
{
    read(n); read(l); read(m);
    pw[0]=1; for(int i=1;i<=l;i++) pw[i]=(ll)pw[i-1]*31%mod;

    mn[root=n+1]=-inf; s[root]=-inf;
    s[son[root][1]=n+2]=mn[n+2]=mx[n+2]=mx[root]=inf; fa[n+2]=root;

    for(int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        for(int j=1;j<=l;j++)
        {
            int p=str[j]-'a'+1; st[i][j]=p;
            add(s[i],(ll)pw[j]*p%mod);
        }
        ins(i);
    }
    while(m--)
    {
        int aa,bb,cc,dd; read(aa); read(bb); read(cc); read(dd);
        erase(aa); 
        if(aa!=cc) erase(cc);
        s[aa]=((ll)s[aa]-(ll)pw[bb]*st[aa][bb]%mod+mod)%mod;
        s[cc]=((ll)s[cc]-(ll)pw[dd]*st[cc][dd]%mod+mod)%mod;

        swap(st[aa][bb],st[cc][dd]);
        add(s[aa],(ll)pw[bb]*st[aa][bb]%mod);
        add(s[cc],(ll)pw[dd]*st[cc][dd]%mod);
        ins(aa); 
        if(aa!=cc) ins(cc);
    }
    for(int i=1;i<=n;i++)
    {
        splay(i,root);
        printf("%d
",ans[i]);
    }

    return 0;
}