bzoj1125:[POI2008]Poc

传送门

这个题好难卡啊。

看到这种题自然会想到字符串hash是不是，但是对于每次操作造成的影响需要\(O(n)\)的时间去更新，自然是不优的

可以发现这个更新可以用数据结构来维护，对于每个hash值开一颗线段树之类的支持区间修改的数据结构

然后就可以愉快的解决了

注意：

1、hash值请使用map和unsigned long long存，否则会产生冲突

2、特判a==c的情况

3、map是真的慢，请不要在无\(O(2)\)情况下使用

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<map>

using namespace std;

void read(int &x) {

    char ch; bool ok;

    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;

    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;

}

#define rg register

#define ull unsigned

const int maxn=1e3+10,k=233,mod=1e5+7;

int n,l,m,id,now,ans[maxn],la[mod*20],ls[mod*20],rs[mod*20];char ch[maxn][110];

bool vis[mod*20];

struct oo

{

	void update(int x){vis[x]=vis[ls[x]]|vis[rs[x]];}

    void pushdown(int x)

    {

        if(vis[ls[x]])la[ls[x]]=max(la[ls[x]],la[x]);

        if(vis[rs[x]])la[rs[x]]=max(la[rs[x]],la[x]);

        la[x]=0;

    }

    void add(int &k,int l,int r,int a,int b)

    {

        if(!k)k=++id;int mid=(l+r)>>1;

        if(l==r){ans[l]=max(ans[l],la[k]);vis[k]=b==1;return ;}

        if(la[k])pushdown(k);

        if(a<=mid)add(ls[k],l,mid,a,b);

        else add(rs[k],mid+1,r,a,b);

        update(k);

    }

    int get(int x,int l,int r,int a)

    {

        int mid=(l+r)>>1;

        if(l==r)return max(ans[l],la[x]);if(la[x])pushdown(x);

        if(a<=mid)return get(ls[x],l,mid,a);

        else return get(rs[x],mid+1,r,a);

    }

};

map<ull,oo>h;

map<int,ull>w,ny;

map<ull,int>sum,rt;

int main()

{

    read(n),read(l),read(m);

    for(rg int i=1;i<=n;i++)scanf("%s",ch[i]+1);ny[0]=1;

    for(rg int i=1;i<=l;i++)ny[i]=ny[i-1]*k;

    for(rg int i=1;i<=n;i++)

    {

        ull now=0;

        for(rg int j=1;j<=l;j++)now=now*k+ch[i][j]-'a';

        w[i]=now,h[now].add(rt[now],1,n,i,1),sum[now]++,la[rt[now]]=max(la[rt[now]],sum[now]);

    }

    for(rg int i=1,a,b,c,d;i<=m;i++)

    {

        read(a),read(b),read(c),read(d);swap(ch[a][b],ch[c][d]);

        if(a!=c)

        {

            h[w[a]].add(rt[w[a]],1,n,a,-1),h[w[c]].add(rt[w[c]],1,n,c,-1),sum[w[a]]--,sum[w[c]]--;

            w[a]=w[a]+(ch[a][b]-ch[c][d])*ny[l-b],w[c]=w[c]+(ch[c][d]-ch[a][b])*ny[l-d];

            h[w[a]].add(rt[w[a]],1,n,a,1),sum[w[a]]++,la[rt[w[a]]]=max(la[rt[w[a]]],sum[w[a]]);

            h[w[c]].add(rt[w[c]],1,n,c,1),sum[w[c]]++,la[rt[w[c]]]=max(la[rt[w[c]]],sum[w[c]]);

        }

        else

        {

            h[w[a]].add(rt[w[a]],1,n,a,-1),h[w[c]].add(rt[w[c]],1,n,c,-1),sum[w[a]]--;

            w[a]=w[a]+(ch[a][b]-ch[c][d])*ny[l-b],w[c]=w[c]+(ch[c][d]-ch[a][b])*ny[l-d];

            h[w[a]].add(rt[w[a]],1,n,a,1),sum[w[a]]++,la[rt[w[a]]]=max(la[rt[w[a]]],sum[w[a]]);

        }

    }

    for(rg int i=1;i<=n;i++)printf("%d\n",h[w[i]].get(rt[w[i]],1,n,i));

}

巴特西

bzoj1125:[POI2008]Poc

传送门

最新文章

热门文章