pb_ds的内容稍微了解了一下， 参考博客：
http://blog.csdn.net/wjf_wzzc/article/details/38851703
红黑树运用
tree binary-search
English Vietnamese
In this problem, you have to maintain a dynamic set of numbers which support the two fundamental operations
INSERT(S,x): if x is not in S, insert x into S
DELETE(S,x): if x is in S, delete x from S
and the two type of queries
K-TH(S) : return the k-th smallest element of S
COUNT(S,x): return the number of elements of S smaller than x
Input
Line 1: Q (1 ≤ Q ≤ 200000), the number of operations
In the next Q lines, the first token of each line is a character I, D, K or C meaning that the corresponding operation is INSERT, DELETE, K-TH or COUNT, respectively, following by a whitespace and an integer which is the parameter for that operation.
If the parameter is a value x, it is guaranteed that 0 ≤ |x| ≤ 109. If the parameter is an index k, it is guaranteed that 1 ≤ k ≤ 109.
Output
For each query, print the corresponding result in a single line. In particular, for the queries K-TH, if k is larger than the number of elements in S, print the word ‘invalid’.
Example
Input
8
I -1
I -1
I 2
C 0
K 2
D -1
K 1
K 2
Output
1
2
2
invalid
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds; //声明
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t; //第一个元素表示key的类型，第二个元素表示value类型， less是排序规则， rb_tree_tag表示红黑树（其他类型的树名称参考原博客）， 最后一个元素表示有序排列int main()
{int n;scanf("%d", &n);char op[4];int x;for(int i = 0; i < n; i++){scanf("%s%d", op, &x);if(op[0] == 'I'){t.insert(x);}else if(op[0] == 'D'){t.erase(x);}else if(op[0] == 'K'){if(t.size()<=x)printf("%d\n", *t.find_by_order(x-1)); //找到第x大的元素，find_by_order()函数返回指针， 从0开始elseprintf("invalid\n");}else{printf("%d\n", t.order_of_key(x)); // order_of_key()返回数组中比x小的元素的个数}}return 0;
}关于字符串hash的内容可以看卿学姐的b站视频：https://www.bilibili.com/video/av7230433/?from=search&seid=3943208075415667641
讲的还是挺好的
或者直接参考卿学姐用的PPT：https://pan.baidu.com/s/1c27PEF2
乌鲁木齐网络赛
Query on a string
You have two strings SS and TT in all capitals.
Now an efficient program is required to maintain a operation and support a query.
The operation C~i~chC i ch with given integer ii and capital letter chch, changes the ii-th character of SS into chch.
The query Q~i~jQ i j asks the program to find out, in the substring of SS from the ii-th character to the jj-th one, the total number of TT appearing.
Input Format
The first line contains an integer TT, indicating that there are TT test cases.
For each test case, the first line contains an integer N~(N \leq 100000)N (N≤100000).
The second line is the string S~(|S| \leq 100000)S (∣S∣≤100000) and the third line is the string T~(|T| \leq 10)T (∣T∣≤10).
Each of the following NN lines provide a operation or a query as above descriptions.
Output Format
For each query, output an integer correponding to the answer.
Output an empty line after each test case.
样例输入
1
5
AABBABA
AA
Q 1 3
C 6 A
Q 2 7
C 2 B
Q 1 5
样例输出
1
2
0
hash + 暴力
待检测版代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int mlen = 15;
//原来的kmp+树状数组有两个问题： 1、kmp在母串长度很小时优化不了多少； 2、复杂度多出一个常数（算复杂度要多试一下）
//hash注意： 1、value的值与k的次数的关系，开long long； 2、如果还是有重复，改一下k值就好了
typedef long long ll;
ll sta;
char s[maxn], t[maxn];
int a[maxn], tree[maxn];
int slen, tlen, q;
const int k = 8;
ll id(string s){ll ans = 0, plus = 1;for(int i = s.size()-1; i>=0; i--){ans += plus*(s[i]-'a');plus*=k;}return ans;
}int jud(int u, int len){char c[15];for(int i = 0; i < len && u < slen; i++){c[i] = s[u++];}c[len] = '\0';string s = c;if(id(s) == sta) return 1;return 0;
}void init(){memset(a, 0, sizeof(a));memset(tree, 0, sizeof(tree));string _t = t;sta = id(_t);
}void update(int s, int c){while(s<=slen){tree[s] += c;s += s&-s;}
}int query(int s){int ans = 0;while(s > 0){ans += tree[s];s -= s&-s;}return ans;
}int main()
{int tt;scanf("%d", &tt);while(tt--){scanf("%d", &q);scanf("%s%s", s, t);slen = strlen(s);tlen = strlen(t);init();for(int i = 0; i <= slen - tlen; i++){int j = jud(i, tlen);if(j){a[i+1] = 1;update(i+1, 1);}}while(q--){char op[4];scanf("%s", op);if(op[0] == 'Q'){int u, v;scanf("%d%d", &u, &v);if(v-u+1 < tlen) printf("0\n");else printf("%d\n", query(v-tlen+1)-query(u-1));}else{int pos; char ch[4];scanf("%d%s", &pos, ch);if(s[pos-1] == ch[0] || pos >= slen) continue;s[pos-1] = ch[0];for(int i = max(0, pos-1-tlen+1); i < pos; i++){if(a[i]) update(i+1, -1);a[i] = jud(i, tlen);if(a[i]) update(i+1, 1);}}}}return 0;
}