凡科网站建站教程,泰安市平台公司,数据可视化网站,网页制作教程古诗词Paper Grading
题意#xff1a;给定nnn个字符串#xff0c;有两种操作#xff1a;
一、给定i,ji, ji,j#xff0c;交换第iii个跟第jjj个字符串。
二、给定 str #xff0c;k,l,rk, l, rk,l,r#xff0c;问你在区间[l,r][l, r][l,r]中的字符#xff0c;与 str 至少有k…Paper Grading
题意给定nnn个字符串有两种操作
一、给定i,ji, ji,j交换第iii个跟第jjj个字符串。
二、给定 str k,l,rk, l, rk,l,r问你在区间[l,r][l, r][l,r]中的字符与 str 至少有kkk个公共前缀的字符串有多少个。
先建立一颗字典树对于满足要求的字符串我们可以在字典树中查找 str 的第 kkk 个字符落在的点rtrtrt
然后在以 rtrtrt 为根的子树上查找在区间[l,r][l, r][l,r]的字符有多少个
考虑在字典树dfsdfsdfs序上对每个节点建立一颗主席树然后插入值对于查询操作我们只要查找两颗主席树上[l,r][l, r][l,r]区间的和即可。
但是因为有带修操作所以考虑树状数组套主席树这样即可满足带修跟查找操作发现一直wa7wa\ 7wa 7据我判断应该是内存不够。
所以考虑如何优化对于字典树来说总长度可以说是固定的2×1052 \times 10 ^ 52×105但是对于nnn来说却是一般小于2×1052 \times 10 ^52×105的对于上述的建树方式
我们建立的主席树可以说也是固定的2×1052 \times 10 ^ 52×105棵所以说整体来说是2×105lognlogn2 \times 10 ^ 5 \log n \log n2×105lognlogn
如果对每个字符串建立一颗主席树整体来说应该是nlog2×105log2×105n \log {2 \times 10 ^ 5} \log {2 \times 10 ^ 5}nlog2×105log2×105在多数情况下应该是小于上着的。
所以对于查询我们只要对[l,r][l, r][l,r]区间查询dfsdfsdfs序在l[rt],r[rt]l[rt], r[rt]l[rt],r[rt]之间的即可对于修改操作我们交换i,ji, ji,j位置的dfsdfsdfs序即可。
#include bits/stdc.husing 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;
}
