[2019 ICPC 南京F]Paper Grading

题目链接

Solution

对 $s_1,s_2,\ldots,s_n$ 建一棵 Trie 树，每个 Trie 树的节点上是一棵线段树。首先这样考虑：在加入 $s_i$ 时，它在 Trie 树上会经过一系列节点，把这些节点的线段树的第 $i$ 个位置均加 $1$，那么询问时，我们只需要沿着 Trie 树找到第 $k$ 个节点，询问这个节点上的线段树中区间 $[l,r]$ 的和是多少。但是这样做的问题在于交换 $s_i,s_j$ 时，我们需要修改两条串经过的路径上的全部线段树，这样的时间开销无疑是不行的。

总的来看，现在的操作是：在 Trie 树上进行路径修改、单点查询。采用树上差分，那么操作可以变为单点修改、子树查询。于是再用一个树状数组维护 dfs 序即可。

所以这道题是 Trie 树的 dfs 序上建树状数组套值域线段树。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n, m, nowid[N], en[N];
string s[N];

int tot;
struct segTree{
	int lson, rson, size;
}tr[N*150];
inline void pushup(int id){
	tr[id].size = tr[tr[id].lson].size + tr[tr[id].rson].size;
}
void add(int id, int l, int r, int pos, int val){
	if(l == r){ tr[id].size += val; return; }
	int mid = (l + r) >> 1;
	if(pos <= mid){
		if(!tr[id].lson)	tr[id].lson = ++tot;
		add(tr[id].lson, l, mid, pos, val);
	}
	else{
		if(!tr[id].rson)	tr[id].rson = ++tot;
		add(tr[id].rson, mid+1, r, pos, val);
	}
	pushup(id);
}
int sum(int id, int l, int r, int L, int R){
	if(id == 0)	return 0;
	if(l == L && r == R)	return tr[id].size;
	int mid = (l + r) >> 1;
	if(R <= mid)	return sum(tr[id].lson, l, mid, L, R);
	else if(L > mid)	return sum(tr[id].rson, mid+1, r, L, R);
	else	return sum(tr[id].lson, l, mid, L, mid) + sum(tr[id].rson, mid+1, r, mid+1, R);
}

struct Trie{
	int ch[26], root; // cntEnd can be changed according to different problem
}trie[N];
#define trie_root 0
int trie_tot;
void insertTrie(string s, int id){
	int len = s.size();
	int now = trie_root;
	for(int i = 0; i < len; i++){
		if(!trie[now].ch[s[i]-'a']){
			trie[now].ch[s[i]-'a'] = ++trie_tot;
			trie[trie_tot].root = ++tot;
		}
		now = trie[now].ch[s[i]-'a'];
	}
	en[id] = now;
}
int st[N], ed[N], dfsClock, fdfn[N];
void dfsTrie(int x){
	st[x] = ++dfsClock;
	fdfn[dfsClock] = x;
	for(int i = 0; i < 26; i++)
		if(trie[x].ch[i])
			dfsTrie(trie[x].ch[i]);
	ed[x] = dfsClock;
}

inline int lowbit(int x){ return x & -x; }
void addBIT(int x, int pos, int val){
	while(x <= trie_tot + 1){
		add(trie[fdfn[x]].root, 1, n, pos, val);
		x += lowbit(x);
	}
}
int sumBIT(int x, int l, int r){
	int res = 0;
	while(x){
		res += sum(trie[fdfn[x]].root, 1, n, l, r);
		x -= lowbit(x);
	}
	return res;
}

void addstr(int id, int pos, int val){
	addBIT(st[en[id]], pos, val);
}
int solve(string s, int l, int r, int k){
	int now = trie_root;
	for(int i = 0; i < k; i++){
		now = trie[now].ch[s[i]-'a'];
		if(!now)	return 0;
	}
	return sumBIT(ed[now], l, r) - sumBIT(st[now]-1, l, r);
}

int main(){
	trie[trie_root].root = ++tot;
	read(n, m);
	for(int i = 1; i <= n; i++){
		cin >> s[i];
		insertTrie(s[i], nowid[i] = i);
	}
	dfsTrie(trie_root);
	for(int i = 1; i <= n; i++)	addstr(i, i, 1);
	while(m--){
		int opt; read(opt);
		if(opt == 1){
			int i, j; read(i, j);
			addstr(nowid[i], i, -1), addstr(nowid[j], j, -1);
			addstr(nowid[i], j, 1), addstr(nowid[j], i, 1);
			swap(nowid[i], nowid[j]);
		}
		else{
			string t; int k, l, r; cin >> t; read(k, l, r);
			printf("%d\n", solve(t, l, r, k));
		}
	}
	return 0;
}