CF547E Mike and Friends (AC 自动机+树状数组）

做法

首先在线算法 是不好搞的
我们先差分 离线询问
我们先用通过ac自动机 求出每个点的fail指针
dfs求出每个子树的大小 和dfn[n]
每个字符串在所有串的出现次数 其实就是他的终止节点 再fail树的子树的贡献
所以我们 需要单点修改 区间查询
用树状数组 维护即可

注意树状数组维护的 字典的 节点个数 不是n 因为这个调了好一会
注意函数别写重名了

#include 
using namespace  std;
//#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1<<62
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e4 + 7;
const int N = 1e4 + 10;
int n, m;
ll dp[N][N];

struct acam {
	struct node {
		int fail;
		int f = 0;
		int son[26] = {};
	} trie[N];
	int idx = 0;
	map<int, int>mp;
	int fa[N];
	void insert(string &s, int id) {
		int u = 0;
		for(auto c : s) {
			if(!trie[u].son[c - 'a']) {
				fa[trie[u].son[c - 'a'] = ++idx] = u ;
			}
			u = trie[u].son[c - 'a'];
		}
		mp[id] = u;
	}
	int cnt = 0;
	int siz[N];
	int dfn[N];
	vi g[N];
	void addedge(int a, int b) {
		g[a].push_back(b);
	}
	void dfs(int x) {
		dfn[x] = ++cnt;
		siz[x] = 1;
		for(auto v : g[x]) {
			dfs(v);
			siz[x] += siz[v];
		}
	}

	void build() {
		queue<int>q;
		for(int i = 0; i <= 25; i++) {
			if(trie[0].son[i]) {
				q.push(trie[0].son[i]);
			}
		}
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(int i = 0; i <= 25; i++) {
				int v = trie[u].son[i], fa = trie[trie[u].fail].son[i];
				if(trie[u].son[i]) {
					trie[v].fail = fa;
					q.push(v);
				} else {
					trie[u].son[i] = trie[trie[u].fail].son[i];
				}
			}
		}
		for(int i = 1; i <= idx; i++) addedge(trie[i].fail, i);

		dfs(0);
	}
		struct BIT {
			int n;
			//n = idx + 1;
			int c[N];
			void reset(int len) {
				n = len;
			}
			void  init(int len, int a[]) {
				n = len;
				for(int i = 1; i <= n; i++) {
					c[i] += a[i];
					if(i + (i & (-i)) <= n)c[i + (i & -i)] += c[i];
				}
			}
			void  add(int x, int k) {
				for(; x <= n; x += x & -x)c[x] += k;
			}
			int  query(int x) {
				int res = 0;
				for(; x; x -= x & -x)res += c[x];
				return res;
			}
		} B;
	
	void change(int id) {
		int  x = mp[id];
		while(x) {
			B.add(dfn[x], 1);
			x = fa[x];
		}
	}
	int query(int id) {
		int k = mp[id];
		return B.query(dfn[k] + siz[k] - 1) - B.query(dfn[k] - 1);
	}
} AC;
int ans[N];
vector<array<int, 3>>  q[N];
void solve() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		AC.insert(s, i);
	}
	AC.build();
	AC.B.reset(AC.idx + 1);
//	cout<
	fer(i, 1, m) {
		int l, r, x;
		cin >> l >> r >> x;
		q[r].push_back({x, i, 1});
	  if(l>1)q[l - 1].push_back({x, i, -1});
	}
	for(int i = 1; i <= n; i++) {
		AC.change(i);
		for (auto v : q[i]) {
			ans[v[1]] += ( v[2] * AC.query(v[0]) );
		}
	}
	for(int i = 1; i <= m; i++) {
		cout << ans[i] << endl;
	}

}


int main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
}






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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163