最近天天做水题……

Description

有若干次向集合中添加01串的操作, 还有一些询问, 问在执行完$[1,a-1]$的添加操作后, 在执行$[a,b]$的操作过程中, 询问串的匹配长度(必须和整个的集合串匹配)变长了多少次.

Solution

把原串建Trie树, 结尾打上时间戳.

把询问离线出来, 然后拿到Trie树上跑, 一路跑一路收集时间标记. 然后拿出来排个序, 取合法且能让长度变长的节点, 数个数就行了.

当然也可以单调栈. 然后取一段合法区间就好了.

这玩意卡空间而且还贼离谱.

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 35e+6 + 5;

int m, arr[35], tmp[10], L;
int tr[maxn][2], tag[maxn], ptr, tot;
struct node {
  int tim, len;
  inline bool operator<(const node &rhs) const {
    return tim < rhs.tim;
  }
}pas[40];
unsigned int qval[1000005];
int qmx[1000005], qmn[1000005];

void Insert(int *str, int len, int idx) {
  int now = 0;
  for (int i = 1; i <= len; ++i) {
    if (!tr[now][str[i]])
      tr[now][str[i]] = ++tot;
    now = tr[now][str[i]];
  }
  tag[now] = idx;
}
void query(int *str, int mx) {
  int now = 0; ptr = 0;
  for (int i = 1; i <= 32; ++i) {
    if (!tr[now][str[i]]) break;
    now = tr[now][str[i]];
    if (tag[now] && tag[now] <= mx) {
      pas[++ptr] = (node){tag[now], i};
    }
  }
}
inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}

int main() {
  m = rd();
  int atr = 0, qtr = 0;
  char opt[5];
  for (int j = 1; j <= m; ++j) {
    scanf("%s", opt);
    if (opt[0] == 'A') {
      atr++;
      unsigned int val = 0;
      for (int i = 3; ~i; --i)
        tmp[i] = rd(), val += (unsigned(tmp[i]) << (8 * i));
      L = rd();
      for (int i = 0; i < 32; ++i)
        arr[32 - i] = ((val & (1 << i)) ? 1 : 0);
      /*for (int i = 1; i <= 32; ++i)
        printf("%d", arr[i]);
      puts("");*/
      Insert(arr, L, atr);
    } else {
      qtr++;
      for (int i = 3; ~i; --i)
        tmp[i] = rd(), qval[qtr] += (unsigned(tmp[i]) << (8 * i));
      qmn[qtr] = rd(); qmx[qtr] = rd();
    }
  }
  for (int i = 1; i <= qtr; ++i) {
    for (int j = 0; j < 32; ++j)
      arr[32 - j] = ((qval[i] & (1 << j)) ? 1 : 0);
    query(arr, qmx[i]);
    sort(pas + 1, pas + 1 + ptr);
    int lst = -1, ans = 0;
    for (int j = 1; j <= ptr; ++j) {
      if (lst < pas[j].len) {
        lst = pas[j].len;
        if (pas[j].tim >= qmn[i]) ans++;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}