Paper Grading

題意：給定$n$個(gè)字符串，有兩種操作：

一、給定$i,j$，交換第$i$個(gè)跟第$j$個(gè)字符串。

二、給定 str ，$k,l,r$，問你在區(qū)間$[l,r]$中的字符，與 str 至少有$k$個(gè)公共前綴的字符串有多少個(gè)。

先建立一顆字典樹，對(duì)于滿足要求的字符串，我們可以在字典樹中查找 str 的第 $k$ 個(gè)字符落在的點(diǎn)$rt$，

然后在以 $rt$ 為根的子樹上查找在區(qū)間$[l,r]$的字符有多少個(gè)，

考慮在字典樹$dfs$序上，對(duì)每個(gè)節(jié)點(diǎn)建立一顆主席樹，然后插入值，對(duì)于查詢操作，我們只要查找兩顆主席樹上$[l,r]$區(qū)間的和即可。

但是因?yàn)橛袔薏僮?#xff0c;所以考慮樹狀數(shù)組套主席樹，這樣即可滿足帶修跟查找操作，發(fā)現(xiàn)一直$wa7$，（據(jù)我判斷應(yīng)該是內(nèi)存不夠）。

所以考慮如何優(yōu)化，對(duì)于字典樹來(lái)說(shuō)，總長(zhǎng)度可以說(shuō)是固定的$2\times 10^5$，但是對(duì)于$n$來(lái)說(shuō)卻是一般小于$2\times 10^5$的，對(duì)于上述的建樹方式，

我們建立的主席樹可以說(shuō)也是固定的$2\times 10^5$棵，所以說(shuō)整體來(lái)說(shuō)是$2\times 10^5\log n\log n$，

如果對(duì)每個(gè)字符串建立一顆主席樹整體來(lái)說(shuō)應(yīng)該是$n\log 2\times 10^5\log 2\times 10^5$，在多數(shù)情況下應(yīng)該是小于上著的。

所以對(duì)于查詢我們只要對(duì)$[l,r]$區(qū)間，查詢$dfs$序在$l[rt],r[rt]$之間的即可，對(duì)于修改操作我們交換$i,j$位置的$dfs$序即可。

#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;int trie[N][26], cnt = 1;int pos[N], value[N], l[N], r[N], tot, n, m;int root[N], ls[N << 7], rs[N << 7], sum[N << 7], num;int insert(string &str) {int n = str.size(), rt = 1;for (int i = 0; i < n; i++) {if (!trie[rt][str[i] - 'a']) {trie[rt][str[i] - 'a'] = ++cnt;}rt = trie[rt][str[i] - 'a'];}return rt; }void dfs(int rt) {l[rt] = ++tot;for (int i = 0; i < 26; i++) {if (trie[rt][i]) {dfs(trie[rt][i]);}}r[rt] = tot; }void update(int &rt, int l, int r, int x, int v) {if (!rt) {rt = ++num;}sum[rt] += v;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], l, mid, x, v);}else {update(rs[rt], mid + 1, r, x, v);} }int A[50], B[50], cnt1, cnt2;int query_sum(int l, int r, int L, int R) {if (l >= L && r <= R) {int ans = 0;for (int i = 1; i <= cnt1; i++) {ans -= sum[A[i]];}for (int i = 1; i <= cnt2; i++) {ans += sum[B[i]];}return ans;}int mid = l + r >> 1, ans = 0, A1[50], B1[50];if (L <= mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = ls[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = ls[B[i]];}ans += query_sum(l, mid, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}if (R > mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = rs[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = rs[B[i]];}ans += query_sum(mid + 1, r, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}return ans; }inline int lowbit(int x) {return x & (-x); }void add(int pos, int x, int v) {for (int i = pos; i <= n; i += lowbit(i)) {update(root[i], 1, tot, x, v);} }int get_sum(int l, int r, int L, int R) {if (l > r || L > R) {return 0;}cnt1 = cnt2 = 0;for (int i = l - 1; i; i -= lowbit(i)) {A[++cnt1] = root[i];}for (int i = r; i; i -= lowbit(i)) {B[++cnt2] = root[i];}return query_sum(1, tot, L, R); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;string str;for (int i = 1; i <= n; i++) {cin >> str;pos[i] = insert(str);}dfs(1);for (int i = 1; i <= n; i++) {pos[i] = l[pos[i]];value[i] = i;add(value[i], pos[i], 1);}for (int i = 1, op, k, a, b; i <= m; i++) {cin >> op;if (op == 1) {cin >> a >> b;add(value[a], pos[a], -1), add(value[b], pos[b], -1);swap(pos[a], pos[b]);add(value[a], pos[a], 1), add(value[b], pos[b], 1);}else {cin >> str >> k >> a >> b;int rt = 1;for (int j = 0; j < k; j++) {if (!trie[rt][str[j] - 'a']) {rt = -1;break;}rt = trie[rt][str[j] - 'a'];}if (rt == -1) {cout << "0\n";}else {cout << get_sum(a, b, l[rt], r[rt]) << "\n";}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2019 ICPC 南京 F. Paper Grading（字典树dfs序上树套树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。