nocriz – nocriz

题目来源：

https://blog.csdn.net/u011056504/article/details/80006052

#include <queue>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define debug(x) cerr<<#x<<'='<<x<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();int f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
const int N = 600060;
vector<int> G[N],ed[N];
int n;
char str[N];
struct Seg{
	ll quad[N*4],lin[N*4],lazy[N*4],sumc[N*4];
	ll get_quad(int num,int l,int r){
		return quad[num]+(2*lin[num]+lazy[num]*(sumc[r]-sumc[l-1]))*lazy[num];//(x+y)^2 = x^2+2*x*y+y*2
	}
	void modify(int num,int l,int r,int ql,int qr){
		
		if(r<ql||l>qr)return;
		if(ql<=l && r<=qr){
			
			lazy[num]+=1;
			//cout<<"FIN OP\t id:"<<num<<'['<<l<<','<<r<<"] q:["<<ql<<','<<qr<<']'<<quad[num]<<' '<<lin[num]<<' '<<lazy[num]<<"  length:"<<sumc[r]-sumc[l-1]<<endl;
			return;
		}
		quad[num] = get_quad(num,l,r);
		lin[num] = lin[num]+lazy[num]*(sumc[r]-sumc[l-1]);
		lazy[num*2]+=lazy[num];lazy[num*2+1]+=lazy[num];lazy[num] = 0;
		int mid = (l+r)/2;
		modify(num*2,l,mid,ql,qr);
		modify(num*2+1,mid+1,r,ql,qr);
		lin[num] = lin[num*2]+lazy[num*2]*(sumc[mid]-sumc[l-1])+lin[num*2+1]+lazy[num*2+1]*(sumc[r]-sumc[mid]);
		quad[num] = get_quad(num*2,l,mid)+get_quad(num*2+1,mid+1,r);
		//cout<<"FIN OP\t id:"<<num<<'['<<l<<','<<r<<"] q:["<<ql<<','<<qr<<']'<<quad[num]<<' '<<lin[num]<<' '<<lazy[num]<<"  length:"<<sumc[r]-sumc[l-1]<<endl;
		
	}
}sgt;
struct automaton{
	int ch[N][26] = {0},mlen[N] = {0},fa[N] = {-1},la = 0,tot = 1;
	void extend(int x){
		//cout<<"EXTEND : "<<x<<" : "<<la<<endl;
		if(ch[la][x]){
			//cout<<"FND"<<endl;
			int p = ch[la][x];
			if(mlen[p] == mlen[la]+1){
				la = p;
				return;
			}
			int np = tot++;mlen[np] = mlen[la]+1;fa[np] = fa[p];fa[p] = np;
			memcpy(ch[np],ch[p],sizeof(ch[p]));
			int po = la;
			while(ch[po][x] == p) ch[po][x] = np,po = fa[po];
			la = np;
			return;
		}
		int np = tot++;mlen[np] = mlen[la]+1;int cp = la;
		while(cp!=-1 && !ch[cp][x]){ch[cp][x] = np;cp = fa[cp];}
		int q = ch[cp][x];
		if(cp == -1){
			fa[np] = 0;
		}else{
			if(mlen[q] == mlen[cp]+1){
				fa[np] = q;
			}else{
				int nq = tot++;mlen[nq] = mlen[cp]+1;fa[nq] = fa[q];
				memcpy(ch[nq],ch[q],sizeof(ch[q]));
				fa[q] = nq;fa[np] = nq;
				for(int cpo = cp;ch[cpo][x] == q;cpo = fa[cpo])ch[cpo][x] = nq;
			}
		}
		la = np;
	}
}sam;
int sz[N],hson[N],dfn[N],ord[N],top[N],depth[N],fa[N],tim = 1;
void dfs(int num){
	hson[num] = -1;
	sz[num] = 1;
	for(auto ct:G[num]){
		depth[ct] = depth[num]+1;
		fa[ct] = num;
		dfs(ct);
		if(hson[num] == -1 || sz[ct]>sz[hson[num]])hson[num] = ct;
		sz[num]+=sz[ct];
	}
}
void dfs2(int num){
	top[num] = (num == hson[fa[num]])?top[fa[num]]:num;
	dfn[num] = tim++;
	sgt.sumc[dfn[num]] = sgt.sumc[dfn[num]-1]+sam.mlen[num]-sam.mlen[fa[num]];
	//cout<<num<<' '<<dfn[num]<<' '<<sgt.sumc[dfn[num]]<<endl;
	if(hson[num]!=-1)dfs2(hson[num]);
	for(auto ct:G[num]){
		if(ct!=hson[num])dfs2(ct);
	}
}
void modify(int x){
	if(!x)return;
	//cout<<top[x]<<' '<<x<<','<<dfn[top[x]]<<' '<<dfn[x]<<endl;
	sgt.modify(1,2,sam.tot,dfn[top[x]],dfn[x]);
//	debug(sgt.quad[1]);
	modify(fa[top[x]]);
}
int main() {
	read(n);
	for(int i=0;i<n;i++){
		scanf("%s",str);
		int m = strlen(str);
		sam.la = 0;
		for(int j=0;j<m;j++){
			sam.extend(str[j]-'a');
			ed[i].push_back(sam.la);
		}
	}
	for(int i=1;i<sam.tot;i++){
		//cout<<sam.fa[i]<<"->"<<i<<endl;
		G[sam.fa[i]].push_back(i);
	}
	dfs(0);hson[0] = -1;
	dfs2(0);
	for(int i=0;i<n;i++){
		for(int j=0;j<ed[i].size();j++){
	//		cout<<i<<' '<<j<<' '<<ed[i][j]<<endl;
			modify(ed[i][j]);
		}
		cout<<sgt.get_quad(1,2,sam.tot)<<endl;
	}
	
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

#include <queue>

#include <cmath>

#include <bitset>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

#define debug(x) cerr<<#x<<'='<<x<<endl

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

template<typename T> void read(T &x){

x = 0;char ch = getchar();int f = 1;

while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}

while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;

}

const int N = 600060;

vector<int> G[N],ed[N];

int n;

char str[N];

struct Seg{

ll quad[N*4],lin[N*4],lazy[N*4],sumc[N*4];

ll get_quad(int num,int l,int r){

return quad[num]+(2*lin[num]+lazy[num]*(sumc[r]-sumc[l-1]))*lazy[num];//(x+y)^2 = x^2+2*x*y+y*2

}

void modify(int num,int l,int r,int ql,int qr){

if(r<ql||l>qr)return;

if(ql<=l && r<=qr){

lazy[num]+=1;

//cout<<"FIN OP\t id:"<<num<<'['<<l<<','<<r<<"] q:["<<ql<<','<<qr<<']'<<quad[num]<<' '<<lin[num]<<' '<<lazy[num]<<" length:"<<sumc[r]-sumc[l-1]<<endl;

return;

}

quad[num] = get_quad(num,l,r);

lin[num] = lin[num]+lazy[num]*(sumc[r]-sumc[l-1]);

lazy[num*2]+=lazy[num];lazy[num*2+1]+=lazy[num];lazy[num] = 0;

int mid = (l+r)/2;

modify(num*2,l,mid,ql,qr);

modify(num*2+1,mid+1,r,ql,qr);

lin[num] = lin[num*2]+lazy[num*2]*(sumc[mid]-sumc[l-1])+lin[num*2+1]+lazy[num*2+1]*(sumc[r]-sumc[mid]);

quad[num] = get_quad(num*2,l,mid)+get_quad(num*2+1,mid+1,r);

//cout<<"FIN OP\t id:"<<num<<'['<<l<<','<<r<<"] q:["<<ql<<','<<qr<<']'<<quad[num]<<' '<<lin[num]<<' '<<lazy[num]<<" length:"<<sumc[r]-sumc[l-1]<<endl;

}

}sgt;

struct automaton{

int ch[N][26] = {0},mlen[N] = {0},fa[N] = {-1},la = 0,tot = 1;

void extend(int x){

//cout<<"EXTEND : "<<x<<" : "<<la<<endl;

if(ch[la][x]){

//cout<<"FND"<<endl;

int p = ch[la][x];

if(mlen[p] == mlen[la]+1){

la = p;

return;

}

int np = tot++;mlen[np] = mlen[la]+1;fa[np] = fa[p];fa[p] = np;

memcpy(ch[np],ch[p],sizeof(ch[p]));

int po = la;

while(ch[po][x] == p) ch[po][x] = np,po = fa[po];

la = np;

return;

}

int np = tot++;mlen[np] = mlen[la]+1;int cp = la;

while(cp!=-1 && !ch[cp][x]){ch[cp][x] = np;cp = fa[cp];}

int q = ch[cp][x];

if(cp == -1){

fa[np] = 0;

}else{

if(mlen[q] == mlen[cp]+1){

fa[np] = q;

}else{

int nq = tot++;mlen[nq] = mlen[cp]+1;fa[nq] = fa[q];

memcpy(ch[nq],ch[q],sizeof(ch[q]));

fa[q] = nq;fa[np] = nq;

for(int cpo = cp;ch[cpo][x] == q;cpo = fa[cpo])ch[cpo][x] = nq;

}

la = np;

}

}sam;

int sz[N],hson[N],dfn[N],ord[N],top[N],depth[N],fa[N],tim = 1;

void dfs(int num){

hson[num] = -1;

sz[num] = 1;

for(auto ct:G[num]){

depth[ct] = depth[num]+1;

fa[ct] = num;

dfs(ct);

if(hson[num] == -1 || sz[ct]>sz[hson[num]])hson[num] = ct;

sz[num]+=sz[ct];

}

void dfs2(int num){

top[num] = (num == hson[fa[num]])?top[fa[num]]:num;

dfn[num] = tim++;

sgt.sumc[dfn[num]] = sgt.sumc[dfn[num]-1]+sam.mlen[num]-sam.mlen[fa[num]];

//cout<<num<<' '<<dfn[num]<<' '<<sgt.sumc[dfn[num]]<<endl;

if(hson[num]!=-1)dfs2(hson[num]);

for(auto ct:G[num]){

if(ct!=hson[num])dfs2(ct);

}

void modify(int x){

if(!x)return;

//cout<<top[x]<<' '<<x<<','<<dfn[top[x]]<<' '<<dfn[x]<<endl;

sgt.modify(1,2,sam.tot,dfn[top[x]],dfn[x]);

// debug(sgt.quad[1]);

modify(fa[top[x]]);

}

int main() {

read(n);

for(int i=0;i<n;i++){

scanf("%s",str);

int m = strlen(str);

sam.la = 0;

for(int j=0;j<m;j++){

sam.extend(str[j]-'a');

ed[i].push_back(sam.la);

}

for(int i=1;i<sam.tot;i++){

//cout<<sam.fa[i]<<"->"<<i<<endl;

G[sam.fa[i]].push_back(i);

}

dfs(0);hson[0] = -1;

dfs2(0);

for(int i=0;i<n;i++){

for(int j=0;j<ed[i].size();j++){

// cout<<i<<' '<<j<<' '<<ed[i][j]<<endl;

modify(ed[i][j]);

}

cout<<sgt.get_quad(1,2,sam.tot)<<endl;

}

return 0;

}

作者：nocriz

奥利卡的诗

ICPC EC-Final 游记

[SDOI2013]随机数生成器

[Ahoi2013]差异

ICPC焦作赛区游记

NOIP2018游记终版

「BZOJ3262」陌上花开

「BZOJ3757」苹果树

做题

ICPC南京赛区游记