目录

  1. 引言
  2. BZOJ 1125: [POI2008]Poc
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. 题目分析
    7. 代码

引言

BZOJ 1125: [POI2008]Poc 题解

BZOJ 1125: [POI2008]Poc

  • Time Limit: 10 Sec

  • Memory Limit: 162 MB

Description

n列火车,每条有l节车厢。每节车厢有一种颜色(用小写字母表示)。有m次车厢交换操作。求:对于每列火车,在交换车厢的某个时刻,与其颜色完全相同的火车最多有多少。

Input

n l m (2 ≤ n ≤ 1000, 1 ≤ l ≤ 100, 0 ≤ m ≤ 100000) n行字符串,长度为l m行,每行4个数a b c d,a车的第b个字符与c车第d个字符交换。

Output

n个数,在交换车厢的某个时刻,与该车颜色完全相同的火车最多数目。

Sample Input

5 6 7

ababbd

abbbbd

aaabad

caabbd

cabaad

2 3 5 4

5 3 5 5

3 5 2 2

1 2 4 3

2 2 5 1

1 1 3 3

4 1 5 6

Sample Output

3

3

3

2

3

题目分析

好题

据说网上代码都是什么平衡树上打标记?虽然挺有道理,但还是跑不过我……

现在好像还是rank3……

这种差距就不是卡常数能解决的了……

我们考虑这样做,我们发现,需要求完全相同的串的个数,这就是同构性判定,我们很容易想到Hash

我们可以$O(n)$求出所有会出现的Hash值,先把他们离散化一下

然后,我们发现,如果我们直接对每个Hash维护单调栈,那么是不行的,因为串的进入时间不一样,在查询的时候不能用已经操作过许多次的栈来更新答案,因为里面会包含许多本不该包含的信息

这样,难道我们就需要可持久化单调栈了吗?

反正我没试过….但是我知道,由于后添加的栈内元素信息一定是会被包含的(但是元素本身不一定,仔细体会一下这里的含义),所以我们可以对每个元素记录一下它自己进入栈的时间

同时,在每个串被操作的时候,把它取出来更新答案,这时候,我们也对这个串记录一下它是什么时候进入它原来的那个单调栈的,然后直接栈内二分即可更新答案

这样,好像就行了?总之虽然总复杂度好像相同,但是我修改是$O(1)$的,这样也能优化很多?

其实我还有好多优化没有使用……

但是这样写会导致细节非常多,有什么串操作后不变,或是交换同一个串的两个字符,或是这两种情况合在一起,然后最开始和最后全都需要更新一次答案……自己写写吧

代码

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
94
95
96
97
98
99
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
141
142
143
144
145
146
147
148
/**************************************************************
Problem: 1125
User: Renatus
Language: C++
Result: Accepted
Time:1756 ms
Memory:14484 kb
****************************************************************/
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#define maxn 2005
#define maxl 205
#define maxm 200005
#define Hash 998244353
#define M 1000000007
#define ll long long int
#define fi first
#define se second
#define push push_back
#define pop pop_back
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, l, m;
char k[maxn][maxl];
void reads(int x){
char ch = gc();
while (!('a' <= ch && ch <= 'z')) ch = gc();
int now = 0;
while ('a' <= ch && ch <= 'z') k[x][++now] = ch, ch = gc();
k[x][++now] = '\0';
}
struct pii{
int fi, se;
pii(int fi = 0, int se = 0) : fi(fi), se(se){}
bool operator < (const pii b) const{
return (fi == b.fi) ? se < b.se : fi < b.fi;
}
};
int has[maxn], _has[maxn];
int t[maxn];
ll mi[maxl];
void get_hash(int x){
has[x] = 0;
rep(i, 1, l) has[x] = ((ll)has[x] * Hash % M + k[x][i]) % M;
}
struct query{
int x, y, z, w;
query(int x = 0, int y = 0, int z = 0, int w = 0) : x(x), y(y), z(z), w(w){}
}q[maxm];
int line[(maxm << 1) + maxn];
int cnt = 0;
vector<pii> s[(maxm << 1) + maxn];
int siz[(maxm << 1) + maxn]; //当前hash等于下标的串个数
int ans[maxn];
void get_ans(int x){
int h = has[x];
ans[x] = max(ans[x], lower_bound(s[h].begin(), s[h].end(), pii(t[x], 0)) -> se);
}
void remove(int x, int ti){
int h = has[x];
siz[h]--;
while (!s[h].empty() && s[h].back().fi == ti) s[h].pop();
s[h].push(pii(ti, siz[h]));
}
void modify(int x, int y, int ti){
int h = has[x];
h = has[x] = y, siz[h]++, t[x] = ti;
while (!s[h].empty() && (s[h].back().se <= siz[h] || s[h].back().fi == ti)) s[h].pop();
s[h].push(pii(ti, siz[h]));
}//remove和modify需要分离,具体原因自行思考
int main(){
#ifndef ONLINE_JUDGE
freopen("poc.in", "r", stdin);
freopen("poc.out", "w", stdout);
#endif
int x, y, z, w;
read(n), read(l), read(m);
//预处理模块
mi[0] = 1;
rep(i, 1, l) mi[i] = mi[i - 1] * Hash % M;
rep(i, 1, n) reads(i);
rep(i, 1, n) get_hash(i), line[++cnt] = has[i], _has[i] = has[i];
rep(i, 1, m) {
read(x), read(y), read(z), read(w);
int d = k[z][w] - k[x][y];
has[x] = (has[x] + M + mi[l - y] * d % M) % M;
has[z] = (has[z] + M - mi[l - w] * d % M) % M;
swap(k[x][y], k[z][w]);
q[i] = query(x, z, has[x], has[z]);
line[++cnt] = has[x], line[++cnt] = has[z];
}
//离散化模块
sort(line + 1, line + 1 + cnt);
cnt = unique(line + 1, line + 1 + cnt) - line - 1;
rep(i, 1, n) has[i] = _has[i];
rep(i, 1, n) has[i] = lower_bound(line + 1, line + 1 + cnt, has[i]) - line;
rep(i, 1, m){
q[i].z = lower_bound(line + 1, line + 1 + cnt, q[i].z) - line;
q[i].w = lower_bound(line + 1, line + 1 + cnt, q[i].w) - line;
}
//算法工作模块
rep(i, 1, n) siz[has[i]]++, t[i] = 0;
rep(i, 1, n) if (s[has[i]].empty()) s[has[i]].push(pii(0, siz[has[i]]));
rep(i, 1, n) get_ans(i);
rep(i, 1, m){
//注意更新答案与修改的顺序
get_ans(q[i].x), get_ans(q[i].y);
if (q[i].x == q[i].y) {
remove(q[i].y, i), modify(q[i].y, q[i].w, i);
continue;
}//注意特殊判断边界情况
remove(q[i].x, i), remove(q[i].y, i);
modify(q[i].x, q[i].z, i), modify(q[i].y, q[i].w, i);
//需要分离remove和modify,否则可能会弹出有用元素,包含无用信息
}
rep(i, 1, n) get_ans(i);
rep(i, 1, n) printf("%d\n", ans[i]);
return 0;
}