[海军国际项目办公室]游戏

游戏

题目描述

[海军国际项目办公室]游戏_第1张图片
[海军国际项目办公室]游戏_第2张图片

题解

我们可以考虑转化到后缀数组上来。
我们将串 A A A与串 B B B接在一起,将所有后缀按照字典序进行排序。
很明显,对于两个 L C P LCP LCP d d d的串 A , B A,B A,B(这里指原串的某个后缀),当我们的 K ⩽ d K\leqslant d Kd时,这两者从串 A A A的起始点与串 B B B的起始点开始的长度为 d d d的子串是相等的。
而当 K > d K>d K>d时,我们可以根据其前后位置判断它们之间的大小关系。

但我们的答案要求的是使得 A < B AA<B A = B A=B A=B A > B A>B A>B的串的总数,我们考虑如何对其维护。
显然,我们的 K K K是不断增加的,在此过程中,会不断有一些 ( A , B ) (A,B) (A,B)从相等变成存在大小关系,以及还有不断有后缀由于长度不够了而不产生贡献,我们只需要对着两种情况进行维护。
显然,这是可以通过线段树进行维护的。
对于 L C P LCP LCP变得小于 K K K的情况,假设排序后第 i i i个与第 i − 1 i-1 i1个之间的 L C P LCP LCP h i h_{i} hi
那么显然,当 K K K变得大于 h i h_{i} hi后, i i i所在的还未被分开的块中,前部分与后部分会彻底分开,产生前面小于后面的贡献。
后面的 A A A串的失败答案中会加上前面的 B B B串数量,同样,前面 A A A的胜利答案中也会加上后面 B B B串的数量,也就是个区间修改。
而当一个 A A A串或 B B B串的长度不够时,它当然不可能继续产生贡献了,所以我们还得把它所做的贡献从线段树删去,也就是个单点修改。

所以事实上排序后打个线段树就行了 ,根本用不到题解所谓的矩阵
时间复杂度 O ( n log ⁡   n ) O\left(n\log\,n\right) O(nlogn)

源码

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN 400005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;     
const LL INF=0x3f3f3f3f3f3f3f3f;  
const int mo=998244353;
const int inv2=499122177;
const int jzm=2333;
const int n1=50;
const int zero=10000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<LL,int> pii;
template<typename _T>
_T Fabs(_T x){
     return x<0?-x:x;}
template<typename _T>
void read(_T &x){
     
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){
     if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){
     x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){
     putchar('\n');while(x>9){
     putchar((x%10)|'0');x/=10;}putchar(x|'0');}
LL gcd(LL a,LL b){
     return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){
     return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){
     x=add(x,y,p);}
int qkpow(int a,int s,int p){
     int t=1;while(s){
     if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
int n,m,x[MAXN],y[MAXN],z[MAXN],c[MAXN];
int sa[MAXN],rk[MAXN],hei[MAXN],lena,lenb;
char astr[MAXN],bstr[MAXN],str[MAXN];
set<int>s;
set<int>::iterator it;
vector<int>vec[MAXN];
void getSa(){
     
	for(int i=1;i<=n;i++)c[x[i]=str[i]]++;
	for(int i=2;i<=m;i++)c[i]+=c[i-1];
	for(int i=n;i>0;i--)sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1){
     
		int num=0;for(int i=n-k+1;i<=n;i++)y[++num]=i;
		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
		for(int i=1;i<=m;i++)c[i]=0;
		for(int i=1;i<=n;i++)c[x[i]]++,z[i]=x[i];
		for(int i=2;i<=m;i++)c[i]+=c[i-1];
		for(int i=n;i>0;i--)sa[c[x[y[i]]]--]=y[i];
		for(int i=1;i<=n;i++)x[i]=y[i]=0;x[sa[1]]=1;num=1;
		for(int i=2;i<=n;i++)x[sa[i]]=(z[sa[i]]==z[sa[i-1]]&&z[sa[i]+k]==z[sa[i-1]+k])?num:++num;
		if(num==n)break;m=num;
	}
}
void getHi(){
     
	int k=0;for(int i=1;i<=n;i++)rk[sa[i]]=i;
	for(int i=1;i<=n;i++){
     
		if(k)k--;int j=sa[rk[i]-1];
		while(str[i+k]==str[j+k])k++;hei[rk[i]]=k;
	}
} 
class SegmentTree{
     
	private:
		LL sum1[MAXN<<2],sum2[MAXN<<2],lzy1[MAXN<<2],lzy2[MAXN<<2];
		int siz[MAXN<<2],cnt[MAXN<<2];
		void pushup(int rt){
     
			sum1[rt]=sum1[lson]+sum1[rson];
			sum2[rt]=sum2[lson]+sum2[rson];
			siz[rt]=siz[lson]+siz[rson];
			cnt[rt]=cnt[lson]+cnt[rson];
		}
		void pushdown(int rt){
     
			if(lzy1[rt]){
     
				sum1[lson]+=1ll*siz[lson]*lzy1[rt];lzy1[lson]+=lzy1[rt];
				sum1[rson]+=1ll*siz[rson]*lzy1[rt];lzy1[rson]+=lzy1[rt];
				lzy1[rt]=0;
			}
			if(lzy2[rt]){
     
				sum2[lson]+=1ll*siz[lson]*lzy2[rt];lzy2[lson]+=lzy2[rt];
				sum2[rson]+=1ll*siz[rson]*lzy2[rt];lzy2[rson]+=lzy2[rt];
				lzy2[rt]=0;
			}
		}
	public:
		void build(int rt,int l,int r){
     
			if(l==r){
     siz[rt]=(sa[l]<=lena);cnt[rt]=(sa[l]>lena+1);return ;}
			int mid=l+r>>1;build(lson,l,mid);build(rson,mid+1,r);pushup(rt);
		}
		int queryCnt(int rt,int l,int r,int al,int ar){
     
			if(l>ar||r<al||al>ar||l>r)return 0;
			if(al<=l&&r<=ar)return cnt[rt];
			int mid=l+r>>1,res=0;pushdown(rt);
			if(al<=mid)res+=queryCnt(lson,l,mid,al,ar);
			if(ar>mid)res+=queryCnt(rson,mid+1,r,al,ar);
			return res;
		}
		int querySiz(int rt,int l,int r,int al,int ar){
     
			if(l>ar||r<al||al>ar||l>r)return 0;
			if(al<=l&&r<=ar)return siz[rt];
			int mid=l+r>>1,res=0;pushdown(rt);
			if(al<=mid)res+=querySiz(lson,l,mid,al,ar);
			if(ar>mid)res+=querySiz(rson,mid+1,r,al,ar);
			return res;
		}
		LL query1(int rt){
     return sum1[rt];}
		LL query2(int rt){
     return sum2[rt];}
		void modify1(int rt,int l,int r,int al,int ar,int aw){
     
			if(l>r||l>ar||r<al||al>ar)return ;
			if(al<=l&&r<=ar){
     sum1[rt]+=1ll*aw*siz[rt];lzy1[rt]+=aw;return ;}
			int mid=l+r>>1;pushdown(rt);
			if(al<=mid)modify1(lson,l,mid,al,ar,aw);
			if(ar>mid)modify1(rson,mid+1,r,al,ar,aw);
			pushup(rt);
		}
		void modify2(int rt,int l,int r,int al,int ar,int aw){
     
			if(l>r||l>ar||r<al||al>ar)return ;
			if(al<=l&&r<=ar){
     sum2[rt]+=1ll*aw*siz[rt];lzy2[rt]+=aw;return ;}
			int mid=l+r>>1;pushdown(rt);
			if(al<=mid)modify2(lson,l,mid,al,ar,aw);
			if(ar>mid)modify2(rson,mid+1,r,al,ar,aw);
			pushup(rt);
		}
		void insertCnt(int rt,int l,int r,int ai){
     
			if(l>r||l>ai||r<ai)return ;
			if(l==r){
     cnt[rt]=0;return ;}
			int mid=l+r>>1;pushdown(rt);
			if(ai<=mid)insertCnt(lson,l,mid,ai);
			if(ai>mid)insertCnt(rson,mid+1,r,ai);
			pushup(rt);
		}
		void insertSiz(int rt,int l,int r,int ai){
     
			if(l>r||l>ai||r<ai)return ;
			if(l==r){
     siz[rt]=sum1[rt]=sum2[rt]=0;return ;}
			int mid=l+r>>1;pushdown(rt);
			if(ai<=mid)insertSiz(lson,l,mid,ai);
			if(ai>mid)insertSiz(rson,mid+1,r,ai);
			pushup(rt);
		}
}T;
void work(int x){
     
	int siz=vec[x].size();		
	for(int j=0;j<siz;j++){
     
		int t=vec[x][j],al,ar;
		it=s.lower_bound(t);ar=(*it)-1;it--;al=(*it);
		int tmp1=T.queryCnt(1,1,n,t,ar);
		int tmp2=T.queryCnt(1,1,n,al,t-1);
		T.modify1(1,1,n,al,t-1,tmp1);
		T.modify2(1,1,n,t,ar,tmp2);
		if(t^1)s.insert(t);
	}
}
signed main(){
     
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%s\n%s",astr+1,bstr+1);
	lena=(int)strlen(astr+1);lenb=(int)strlen(bstr+1);
	for(int i=1;i<=lena;i++)str[++n]=astr[i];str[++n]='#';
	for(int i=1;i<=lenb;i++)str[++n]=bstr[i];m=126;getSa();getHi();
	for(int i=1;i<=n;i++)vec[hei[i]].pb(i);T.build(1,1,n);
	s.insert(1);s.insert(n+1);work(0);
	for(int i=1;i<=min(lena,lenb);i++){
     
		LL sum1=T.query1(1),sum2=T.query2(1),sum3=1ll*(lena-i+1)*(lenb-i+1),sum4=sum3-sum1-sum2;work(i);
		if(sum1){
     LL d=gcd(sum1,sum3);printf("%lld/%lld ",sum1/d,sum3/d);}else printf("0/1 ");
		if(sum4){
     LL d=gcd(sum4,sum3);printf("%lld/%lld ",sum4/d,sum3/d);}else printf("0/1 ");
		if(sum2){
     LL d=gcd(sum2,sum3);printf("%lld/%lld\n",sum2/d,sum3/d);}else printf("0/1\n");
		T.insertCnt(1,1,n,rk[n-i+1]);T.insertSiz(1,1,n,rk[lena-i+1]);
		T.modify1(1,1,n,1,rk[n-i+1],-1);T.modify2(1,1,n,rk[n-i+1],n,-1);
	} 
	return 0;
}

你可能感兴趣的