A.模拟。
B.模拟。比赛的时候这题出锅了，然后就unrated了。注意要先保证最大值最小，再保证字典序最大。
C.构造。挑一个大于N的质数然后连啊连就可以了。
D.可持久化Trie。弄两个Trie。一个记录字符串，另一个记录数字。
1 #include2 #include 3 #include 4 using namespace std; 5 struct StringTrie { 6 StringTrie *ch[26]; int val; 7 StringTrie() {memset(this, 0, sizeof(*this)); val = -1;} 8 StringTrie* set(int n, const char *str, int p, int v) { 9 StringTrie *res = new StringTrie(); *res = *this;10 if (p >= n) res->val = v;11 else {12 int c = str[p] - 'a';13 if (!ch[c]) ch[c] = new StringTrie();14 res->ch[c] = ch[c]->set(n, str, p + 1, v);15 } return res;16 }17 int query(int n, const char *str, int p) {18 if (p >= n) return val;19 else {20 int c = str[p] - 'a';21 if (!ch[c]) return -1;22 return ch[c]->query(n, str, p + 1);23 }24 }25 } *srt[100005];26 struct BinaryTrie {27 BinaryTrie *ch[2]; int val;28 BinaryTrie() {memset(this, 0, sizeof(*this));}29 BinaryTrie* add(int x, int val, int p) {30 BinaryTrie *res = new BinaryTrie(); *res = *this; res->val += val;31 if (p >= 0) {32 int c = (x >> p) & 1;33 if (!ch[c]) ch[c] = new BinaryTrie();34 res->ch[c] = ch[c]->add(x, val, p - 1);35 } return res;36 }37 int query(int x, int p) {38 if (p < 0) return 0;39 else {40 int c = (x >> p) & 1, res = 0;41 if (c && ch[0]) res += ch[0]->val;42 if (ch[c]) res += ch[c]->query(x, p - 1);43 return res;44 }45 }46 } *brt[100005];47 int main() {48 srt[0] = new StringTrie(); brt[0] = new BinaryTrie();49 int n; scanf("%d", &n); char op[20], str[20];50 for (int v, i = 1; i <= n; ++i) {51 scanf("%s", op);52 if (*op == 's') {53 scanf("%s%d", str, &v); int l = strlen(str);54 int x = srt[i-1]->query(l, str, 0);55 srt[i] = srt[i-1]->set(l, str, 0, v);56 brt[i] = brt[i-1];57 if (~x) brt[i] = brt[i]->add(x, -1, 30);58 brt[i] = brt[i]->add(v, 1, 30);59 } else if (*op == 'r') {60 scanf("%s", str); int l = strlen(str);61 int x = srt[i-1]->query(l, str, 0);62 brt[i] = brt[i-1]; srt[i] = srt[i-1]->set(l, str, 0, -1);63 if (~x) brt[i] = brt[i]->add(x, -1, 30);64 } else if (*op == 'q') {65 scanf("%s", str); int l = strlen(str);66 brt[i] = brt[i-1]; srt[i] = srt[i-1];67 int x = srt[i]->query(l, str, 0);68 if (~x) printf("%d\n", brt[i]->query(x, 30));69 else puts("-1"); fflush(stdout);70 } else {71 scanf("%d", &v); srt[i] = srt[i-v-1]; brt[i] = brt[i-v-1];72 }73 }74 return 0; 75 }
E.跟bzoj上的遥远的国度很类似。