题意

略

分析

把串倒过来插进trietrietrie上, 那么一个串的kpmkpmkpm串就是这个串在trietrietrie上对应的结点的子树下面的所有字符串.

那么像 BZOJ 3551/3545: [ONTAK2010]Peaks加强版用dfsdfsdfs序+主席树就可以O(nlogn)O(nlogn)O(nlogn)解决查找子树第kkk小问题

但是与 BZOJ 3551/3545: [ONTAK2010]Peaks加强版不同的是,这道题可能出现相同的串,于是在trietrietrie树上用链表把编号链起来就行了.

…

sbsbsb了,没想到超水的做法…geng4512的博客

CODE

#include <cctype>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

    char ch; int flg = 1; for(;!isdigit(ch=getc());)if(ch=='-')flg=-flg;

    for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); res*=flg;

}

const int MAXN = 100005;

const int MAXL = 300005;

const int MAXC = 26;

int n, num[MAXN], trie_tot, in[MAXL], out[MAXL], tmr, seq[MAXN]; char s[MAXL];

struct seg { //主席树

	seg *ls, *rs;

	int sum;

	inline void* operator new (size_t, seg *Ls, seg *Rs, int _) {

		static seg *mempool, *C;

		if(C == mempool) mempool = (C = new seg[1<<15]) + (1<<15);

		C->ls = Ls;

		C->rs = Rs;

		C->sum = _;

		return C++;

	}

}*rt[MAXL];

struct O { //链表

	O *nxt;

	int v;

	inline void* operator new(size_t, O *Nxt, int _) {

		static O *mempool, *C;

		if(C == mempool) mempool = (C = new O[1<<15]) + (1<<15);

		C->nxt = Nxt;

		C->v = _;

		return C++;

	}

}*head[MAXL];

struct trie {

	trie *ch[MAXC];

	int v;

	inline void* operator new(size_t) {

		static trie *mempool, *C;

		if(C == mempool) mempool = (C = new trie[1<<15]) + (1<<15);

		C->v = ++trie_tot;

		return C++;

	}

}*root;

inline void add(int x, int v) {

	head[x] = new(head[x], v) O;

}

inline void insert(int id, int i) {

	trie *r = root;

	while(~i) {

		if(!r->ch[s[i]-'a'])

			r->ch[s[i]-'a'] = new trie;

		r = r->ch[s[i]-'a'];

		i--;

	}

	add(num[id] = r->v, id); //用链表链起来

}

void dfs(trie *x) {

	in[x->v] = tmr + 1;

	for(O *i = head[x->v]; i; i = i->nxt)

		seq[++tmr] = i->v;

	for(int i = 0; i < MAXC; ++i)

		if(x->ch[i]) dfs(x->ch[i]);

	out[x->v] = tmr;

}

seg* insert(seg *p, int l, int r, int x) {

	if(l == r) return new(0x0, 0x0, p->sum+1) seg;

	int mid = (l + r) >> 1;

	if(x <= mid) return new(insert(p->ls, l, mid, x), p->rs, p->sum+1) seg;

	else return new(p->ls, insert(p->rs, mid+1, r, x), p->sum+1) seg;

}

inline int query(int i, int k) {

	seg *x = rt[in[i]-1], *y = rt[out[i]];

	if(y->sum - x->sum < k) return -1;

	int l = 1, r = n, mid;

	while(l < r) {

		mid = (l + r) >> 1;

		if(y->ls->sum - x->ls->sum >= k)

			x = x->ls, y = y->ls, r = mid;

		else k -= y->ls->sum - x->ls->sum, x = x->rs, y = y->rs, l = mid+1;

	}

	return l;

}

int main () {

	read(n); root = new trie;

	for(int i = 1; i <= n; ++i) {

		while(!isalpha(s[0]=getc())); int len = 0;

		while(isalpha(s[++len]=getc()));

		insert(i, len-1);

	}

	dfs(root);

	rt[0] = new(0x0, 0x0, 0) seg; //初始化空树

	rt[0]->ls = rt[0]->rs = rt[0];

	for(int i = 1; i <= n; ++i)

		rt[i] = insert(rt[i-1], 1, n, seq[i]);

	for(int i = 1, x; i <= n; ++i)

		read(x), printf("%d\n", query(num[i], x));

}

巴特西

BZOJ 3439: Kpm的MC密码 (trie+dfs序主席树)

题意

分析

CODE

最新文章

热门文章