## 【Codeforces 817E】Choosing The Commander

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009 * 32;

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

class Trie{
int root, cnt;
struct Node{
int sum, ch[2];
}p[N];
public:
inline void modify(int v, int d) {
modify(root, 30, v, d);
}
inline int query(int buf, int lim) {
return query(root, 30, buf, lim);
}
private:
inline void modify(int &w, int t, int v, int d) {
w = w? w: ++cnt;
p[w].sum += d;
if (t >= 0) {
modify(p[w].ch[(v >> t) & 1], t - 1, v, d);
}
}
inline int query(int w, int t, int buf, int lim) {
if (!w || t == -1) {
return 0;
} else {
int ret = 0, t2 = (buf >> t) & 1, t1 = (lim >> t) & 1;
if (t1) {
ret += p[p[w].ch[t2]].sum;
ret += query(p[w].ch[t2 ^ 1], t - 1, buf, lim);
} else {
ret += query(p[w].ch[t2], t - 1, buf, lim);
}
return ret;
}
}
}trie;

int main() {
for (int i = 1; i <= n; i++) {
if (ty == 1) {
} else if (ty == 2) {
} else {
printf("%d\n", trie.query(p, l));
}
}
return 0;
}


## 【BZOJ 4212】神牛的养成计划

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000009;
const int M = 2009;
const int SGZ = 26;

int n,m,tot,beg[M],sz[M],ord[M];
char s1[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

class Trie{
int cnt,ch[N][26],mn[N],mx[N];
vector<int> id[N];
public:
inline void insert(char *s, int len, int ID) {
int w = 0;
for (int i=0;i<len;i++) {
int c = s[i] - 'a';
if (!ch[w]) ch[w] = ++cnt;
w = ch[w];
}
id[w].push_back(ID);
}
inline void sort(int w, int *arr, int &cur) {
for (int i=0;i<id[w].size();i++) {
arr[++cur] = id[w][i];
}
for (int i=0;i<SGZ;i++) {
if (ch[w][i]) {
sort(ch[w][i], arr, cur);
}
}
}
inline void mark(int val, char *s, int len) {
int w = 0;
for (int i=0;i<len;i++) {
int c = s[i] - 'a';
w = ch[w];
if (!mn[w] || mn[w] > val) mn[w] = val;
if (!mx[w] || mx[w] < val) mx[w] = val;
}
}
inline void query(char *s, int len, int &l, int &r) {
int w = 0;
for (int i=0;i<len;i++) {
int c = s[i] - 'a';
if (!ch[w]) {
l = 1; r = 0;
return;
} else {
w = ch[w];
}
}
l = mn[w];
r = mx[w];
}
private:
}trie;

class Persistent_Trie{
int cnt,root[M],sum[N],ch[N][26];
public:
inline void insert(int p, int w, char *s, int len) {
Insert(root[p], root[w], s, len);
}
inline int query(int l, int r, char *s, int len) {
if (l > r) return 0;
int ret = 0, w = root[r];
for (int i=0;i<len;i++) {
w = ch[w][s[i]-'a'];
}
ret += sum[w];
w = root[l-1];
for (int i=0;i<len;i++) {
w = ch[w][s[i]-'a'];
}
ret -= sum[w];
return ret;
}
private:
void Insert(int p, int &w, char *s, int len) {
w = ++cnt;
sum[w] = sum[p] + 1;
memcpy(ch[w], ch[p], sizeof(ch[w]));
if (len <= 0) return;
int c = s[len-1] - 'a';
Insert(ch[p], ch[w], s, len - 1);
}
}PTE;

int main() {
for (int i=1,last=0;i<=n;i++) {
beg[i] = last;
scanf("%s", s1+last);
sz[i] = strlen(s1+last);
trie.insert(s1+last, sz[i], i);
last += sz[i];
}
tot = 0;
trie.sort(0, ord, tot);
for (int i=1;i<=n;i++) {
trie.mark(i, s1+beg[ord[i]], sz[ord[i]]);
PTE.insert(i-1, i, s1+beg[ord[i]], sz[ord[i]]);
}
for (int tt=1,last=0,l,r;tt<=m;tt++) {
scanf("%s",s1);
int len = strlen(s1);
for (int i=0;i<len;i++) {
s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
}
trie.query(s1, len, l, r);
scanf("%s",s1);
len = strlen(s1);
for (int i=0,j=len-1;i<j;i++,j--) {
swap(s1[i], s1[j]);
}
for (int i=0;i<len;i++) {
s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
}
last = PTE.query(l, r, s1, len);
printf("%d\n",last);
}
return 0;
}


## 【BZOJ 3926】[ZJOI2015] 诸神眷顾的幻想乡

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = 2000000;
const int C = 10;

class Suffix_Automaton{
int ch[M][C],pre[M],len[M],cnt;
public:
inline int insert(int last, int t) {
int w = ++cnt; len[w] = len[last] + 1; pre[0] = -1;
for (;~last&&!ch[last][t];last=pre[last]) ch[last][t] = w;
if (~last) {
if (len[ch[last][t]] == len[last] + 1) {
pre[w] = ch[last][t];
} else {
int nw = ++cnt, tmp = ch[last][t];
len[nw] = len[last] + 1;
pre[nw] = pre[tmp]; pre[tmp] = pre[w] = nw;
memcpy(ch[nw],ch[tmp],sizeof(ch[nw]));
for (;~last&&ch[last][t]==tmp;last=pre[last]) ch[last][t] = nw;
}
} return w;
}
inline LL solve() {
LL ret = 0;
for (int i=1;i<=cnt;i++)
ret += len[i] - len[pre[i]];
return ret;
}
}SAM;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v) {
static int E = 1; in[u]++; in[v]++;
}

void DFS(int w, int f, int s) {
int rt = SAM.insert(s, col[w]);
if (to[i] != f) DFS(to[i], w, rt);
}

int main() {
for (int i=1;i<=n;i++) col[i] = read();
for (int i=1;i<=n;i++) if (in[i] == 1) DFS(i, i, 0);
printf("%lld\n",SAM.solve());
return 0;
}


## 【BZOJ 4571】[SCOI2016] 美味

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = N * 18;

int arr[N],n,m,MX;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

namespace Chair_Tree{
#define CT Chair_Tree
int ch[M][2],sum[M],cnt,root[N];
int ans_tmp,L,R;

void build(int p, int &w, int l, int r, int cur) {
w = ++cnt; memcpy(ch[w],ch[p],sizeof(ch[w]));
sum[w] = sum[p] + 1; if (l < r) {
int mid = l + r + 1 >> 1;
if (cur < mid) build(ch[p][0],ch[w][0],l,mid-1,cur);
else build(ch[p][1],ch[w][1],mid,r,cur);
}
}

inline void Build_Tree() {
for (int i=1;i<=n;i++)
build(root[i-1],root[i],0,MX,arr[i]);
}

void ask(int w, int l, int r, int f) {
if (L <= l && r <= R) ans_tmp += sum[w]*f;
else if (w) {
int mid = l + r + 1 >> 1;
}
}

inline int Query(int r1, int r2, int l, int r) {
l = max(0,l); r = min(MX,r);
if (l > r) return 0;

ans_tmp = 0; L = l; R = r;
return ans_tmp;
}

inline int query(int b, int x, int l, int r){
int ret = 0, r1 = root[l-1], r2 = root[r];
for (int i=17;~i;i--) {
int c = (b & (1<<i)) ^ (1<<i);
if (Query(r1,r2,ret+c-x,ret+c+(1<<i)-1-x)) ret += c;
else ret += c ^ (1<<i);
} return ret^b;
}
};

int main(){
for (int i=1;i<=n;i++) MX = max(MX, arr[i]=read());
CT::Build_Tree();
for (int i=1,b,x,l,r;i<=m;i++) {
printf("%d\n",CT::query(b,x,l,r));
}
return 0;
}


## 【BZOJ 4523】[Cqoi2016] 路由表

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const int M = 33000000;

int Stack[N];
bool ip[40];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Trie{
#define TRE Trie
int tot=1,ch[M][2],cnt,root=1,end[M];

inline void modify(int len){
int w = root;
for (int i=1;i<=len;i++) {
int c = ip[i];
if (ch[w]) w = ch[w];
else w = ch[w] = ++tot;
}
end[w] = ++cnt;
}

inline int query(int l, int r){
int top = 0, w = root, t = 1;
while (w) {
if (end[w]) {
while (top && Stack[top] > end[w]) top--;
Stack[++top] = end[w];
}
w = ch[w][ip[t]]; t++;
} t = 0;
for (int i=1;i<=top;i++)
if (Stack[i] > r) break;
else if (Stack[i] >= l) t++;
return t;
}
};

inline void Get_IP(){
memset(ip,0,sizeof(ip));
for (int j=1,sta=9;j<=4;j++,sta+=8) {
int TP = read(), i = 1;
while (TP) ip[sta-i] = TP & 1, TP >>= 1, i++;
}
}

int main(){
char c=getchar();
while (c != 'A' && c != 'Q') c=getchar();
if (c == 'A') {
Get_IP();