Description

https://www.luogu.com.cn/problem/P3471

Solution

数据结构学傻了。算是小清新数据结构题？

判断相同考虑哈希。

我们对每个哈希值维护一个集合，集合按加入时间排序（所以为什么不叫序列呢），集合中的每个点带权表示当这个点加入时刻下的集合大小。我们删除一个点时查询这个点在原来所在集合中的后缀最大值。也就是我们要在线维护：

  • 加入一个数。
  • 查询一个数在集合中的后缀最大值。

显然可以用平衡树搞一搞，那这样不是太平凡了吗？

考虑带权并查集，每次把一个点加入集合时把他作为这个集合的根。查询时做路径压缩的时候，把到根的权值的最大值和自己本身取最大。这样每个点的后缀最大值信息就维护好了。

如果自己写哈希表的话可以做到 $O(nl+m)$。但我比较懒用 unordered_map。

目前是最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7,base=137;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
char s[1005][105];
int w[1005],pw[105],las[1005];
int ans[1005],n,m,l;
unordered_map<int,int>mp;
int cnt;
vector<pair<int,int> >fa[110005];//fi->fa,se->suffix max
int root[110005],siz[110005];
int getfa(int u,int x) {
	// gdb(u,x,fa[u][x].fi,fa[u][x].se);
	if (fa[u][x].fi==x) return fa[u][x].se;
	int tmp=getfa(u,fa[u][x].fi);
	fa[u][x].fi=fa[u][fa[u][x].fi].fi;
	return fa[u][x].se=max(fa[u][x].se,tmp);
}
void calc(int x) {
	ans[x]=max(ans[x],getfa(mp[w[x]],las[x]));
}
void insert(int u,int x,int s) {
	las[x]=fa[u].size();
	// gdb(u,x,s,las[x]);
	fa[u].push_back(mk(las[x],s));
	if (root[u]>=0) fa[u][root[u]].fi=las[x];
	root[u]=las[x];
}
void add(int &x,int y) {x=(x+y)%mod;};
signed main(void){
	freopen("1.in","r",stdin);
	int i,j,x,y,xx,yy;
	read(n);read(l);read(m);
	for (pw[0]=1,i=1;i<=l;i++) pw[i]=pw[i-1]*base%mod;
	memset(root,-1,sizeof(root));
	for (i=0;i<n;i++) {
		scanf("%s",s[i]);
		for (j=0;j<l;j++) w[i]=(w[i]+pw[j]*s[i][j])%mod;
		if (!mp[w[i]]) mp[w[i]]=++cnt;
		siz[mp[w[i]]]++;
	}
	for (i=0;i<n;i++) {
		ans[i]=siz[mp[w[i]]];
		insert(mp[w[i]],i,siz[mp[w[i]]]);
	}
	while (m--) {
		read(x),read(xx),read(y),read(yy);
		x--,xx--,y--,yy--;
		calc(x);calc(y);
		siz[mp[w[x]]]--;
		if (x^y) siz[mp[w[y]]]--;
		add(w[x],pw[xx]*(s[y][yy]-s[x][xx]+mod));
		add(w[y],pw[yy]*(s[x][xx]-s[y][yy]+mod));
		swap(s[x][xx],s[y][yy]);
		if (!mp[w[x]]) mp[w[x]]=++cnt;
		siz[mp[w[x]]]++;
		if (!mp[w[y]]) mp[w[y]]=++cnt;
		if (x^y) siz[mp[w[y]]]++;
		insert(mp[w[x]],x,siz[mp[w[x]]]);
		insert(mp[w[y]],y,siz[mp[w[y]]]);
	}
	for (i=0;i<n;i++) calc(i);
	for (i=0;i<n;i++) printf("%lld\n",ans[i]);
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i