## 【日常小测】String

### 题目大意

1. 在字符串$S$末尾加入一个字符
2. 将$S$的子串$[l,r]$取出来，设为字符串$T$,询问$T$中出现至少两次的字符串的最长长度

## 【UOJ 77】A+B Problem

### Code

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

const int N = 200000+9;
const int M = 2000000;
const int INF = 1000000000;

int tot,_hash[N],A[N],W[N],B[N],LL[N],RR[N],P[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;
}

inline void Add_Edge(int u, int v, int f = INF, int t = 0) {
static int E = 1; vout += f * t;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;

namespace Persistent_Segment_Tree{
#define PST Persistent_Segment_Tree
int ch[N][2],root[N],cnt,pur,sur,L,R;

void insert(int p, int &w, int l, int r, int f = 0) {
if (w = ++cnt, p) {
ch[w][0] = ch[p][0];
ch[w][1] = ch[p][1];
}
if (l < r) {
int mid = l + r + 1 >> 1;
if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, w);
else insert(ch[p][1], ch[w][1], mid, r, w);
}

inline void insert(int p, int v) {
pur = v; sur = p;
insert(root[p-1], root[p], 1, tot);
}

void modify(int w, int l, int r) {
if (!w) return;
else if (L <= l && r <= R) Add_Edge(w, pur);
else {
int mid = l + r + 1 >> 1;
if (L < mid) modify(ch[w][0], l, mid-1);
if (mid <= R) modify(ch[w][1], mid, r);
}
}

inline void modify(int p, int node, int l, int r) {
pur = node; L = l; R = r;
modify(root[p], 1, tot);
}
};

int main() {
n = read(); PST::cnt = n << 1;
S = 0; T = N - 1;
for (int i=1;i<=n;i++) {
}
sort(_hash+1, _hash+1+tot);
tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
for (int i=1;i<=n;i++) {
A[i] = lower_bound(_hash+1, _hash+1+tot, A[i]) - _hash;
LL[i] = lower_bound(_hash+1, _hash+1+tot, LL[i]) - _hash;
RR[i] = lower_bound(_hash+1, _hash+1+tot, RR[i]) - _hash;
}
for (int i=1,l,r;i<=n;i++) {
PST::insert(i, A[i]);
PST::modify(i-1, i+n, LL[i], RR[i]);
}
printf("%d\n",vout-Dinic.MaxFlow());
return 0;
}


## 【CodeChef BTREE】Union on Tree

### 解题报告

##### 1）函数式线段树的做法

1. v不是u在虚树中的祖先，统计v的子树中、到u的距离为d的点的个数
这个的话，直接用函数式线段树查就好
2. v是u的父亲，其余条件相同
这样的话，似乎与v的距离就不固定了（lca在u ~ v中移动）
于是先用点分治做出所有点到u的距离为d的点的个数n1
然后需要减掉v子树外的部分，这样的话，发现到v的距离就固定了
于是减掉所有点到v的距离为d-dis(u,v)的点数n2
再加上v子树中到v距离为d-dis(u,v)的点数n3就可以辣！

### Code

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

const int N = 100000 + 9;
const int M = N << 1;
const int INF = 1e8;

int anc[N][18],dep[N],val[N],p[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;
}

inline void Add_Edge(int u, int v) {
}

void DFS(int w, int f) {
static int cnt = 0;
dep[w] = dep[f] + 1;
anc[w][0] = f; num[w] = ++cnt;
if (!dep[to[i]]) {
DFS(to[i], w);
}
}
}

inline int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i=17;~i;i--)
if (dep[anc[x][i]] >= dep[y])
x = anc[x][i];
if (x == y) return x;
for (int i=17;~i;i--) {
if (anc[x][i] != anc[y][i]) {
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
}

inline int dis(int x, int y) {
int lca = LCA(x, y);
return dep[x] + dep[y] - dep[lca] * 2;
}

class Point_Based_Divide_and_Conquer{
int fa[N][18],tot[N],sum[N];
int ans_tmp,root,block_size;
vector<int> q[N],mul[N];
bool vis[N];

public:
inline void init() {
block_size = n;
ans_tmp = INF;
Get_Root(1, 1);
tot[root] = 1;
build(root, n);
}

inline int query(int w, int rag) {
int ret = Query(w, rag, q);
for (int i=1,t;i<tot[w];i++) {
t = rag - dis(fa[w][i], w);
if (t >= 0) {
ret += Query(fa[w][i], t, q);
ret -= Query(fa[w][i-1], t, mul);
}
}
return ret;
}
private:
void Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
mx = max(mx, sum[to[i]]);
sum[w] += sum[to[i]];
}
}
mx = max(block_size - sum[w], mx);
if (mx < ans_tmp) {
ans_tmp = mx;
root = w;
}
}

void build(int w, int sz) {
vis[w] = 1; fa[w][0] = w;
if (!vis[to[i]]) {
block_size = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
ans_tmp = INF; Get_Root(to[i], w);
memcpy(fa[root]+1, fa[w], sizeof(fa[w])-sizeof(int));
tot[root] = tot[w] + 1;
build(root, block_size);
}
}

if (val[w]) {
for (int i=0;i<tot[w];i++)
q[fa[w][i]].push_back(dis(w, fa[w][i]));
for (int i=0;i<tot[w]-1;i++)
mul[fa[w][i]].push_back(dis(w, fa[w][i+1]));
}
sort(q[w].begin(), q[w].end());
sort(mul[w].begin(), mul[w].end());
}

inline int Query(int w, int r, vector<int> *a) {
return upper_bound(a[w].begin(), a[w].end(), r) - a[w].begin();
}
}PDC;

class Virtual_Tree{
int stk[N],rag[N],top,lca,cnt,root;
queue<int> que;
bool inq[N];

public:
inline void build(int &tot) {
cnt = tot; T = 0;
for (int i=2;i<=tot;i++) {
root = LCA(root, p[i]);
}
static auto cmp = [](int a, int b) {return num[a] < num[b];};
sort(p+1, p+1+tot, cmp);
if (root != p[1]) p[++tot] = root, newnode(root, -1);
stk[top=1] = root;
for (int i=1+(p[1]==root);i<=cnt;i++) {
lca = LCA(p[i], stk[top]);
for (;dep[stk[top]] > dep[lca];top--)
if (dep[stk[top-1]] >= dep[lca]) AddEdge(stk[top-1], stk[top]);
if (lca != stk[top])
stk[++top] = p[++tot] = lca;
if (p[i] != stk[top])
stk[++top] = p[i];
}
for (int i=1;i<top;i++)
}

inline int solve(int tot) {
prework(tot);
int ret = 0;
for (int i=1,u,v,r,mid,t;i<T;i+=2) {
u = to[i]; v = to[i+1];
r = rag[u] + rag[v] - cost[i] >> 1;
if (r >= 0) {
mid = move(u, v, r);
ret -= PDC.query(mid, r);
}
}
for (int i=1;i<=tot;i++)
ret += PDC.query(p[i], rag[p[i]]);
return ret;
}
private:
inline void newnode(int w, int v) {
rag[w] = v << 1;
}

inline int move(int x, int y, int r) {
if (dep[x] < dep[y]) swap(x, y);
r = rag[x] - r;
for (int i=0;r;i++,r>>=1)
if (r & 1) x = anc[x][i];
return x;
}

inline void prework(int tot) {
for (int i=1;i<=tot;i++) {
que.push(p[i]);
inq[p[i]] = 1;
}

while (!que.empty()) {
int w = que.front();
que.pop(); inq[w] = 0;
if (rag[w] > rag[to[i]] + cost[i]) {
rag[to[i]] = rag[w] - cost[i];
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
}

inline void AddEdge(int u, int v) {
int w = dis(u, v);
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}
}VT;

int main() {
fill(val+1, val+1+n, 1);
for (int i=1,lim=n,u,v;i<lim;i++) {
}

DFS(1, 1);
for (int j=1;j<=17;j++) {
for (int i=1;i<=n;i++) {
anc[i][j] = anc[anc[i][j-1]][j-1];
}
}
PDC.init();

for (int y=1,k;y<=m;y++) {
printf("%d\n",VT.solve(k));
}
return 0;
}


## 【BZOJ 2653】middle

### Code

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

const int N = 25000 + 9;
const int M = 400000;

int n,m,tot,arr[N],_hash[N],last_ans;
vector<int> pos_que[N];

namespace Chair_Tree{
#define CT Chair_Tree
int ch[M][2],ls[M],rs[M],sum[M],root[N],cnt;

void Build(int &w, int l, int r) {
sum[w=++cnt] = r - l + 1;
ls[w] = rs[w] = sum[w];
if (l < r) {
int mid = l + r + 1 >> 1;
Build(ch[w][0], l, mid-1);
Build(ch[w][1], mid, r);
}
}inline void init() {Build(root[1],1,n);}

void insert(int p, int &w, int l, int r, int pur) {
sum[w=++cnt] = sum[p] - 2;
memcpy(ch[w],ch[p],sizeof(ch[w]));
if (l < r) {
int mid = l + r + 1 >> 1;
if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, pur);
else insert(ch[p][1], ch[w][1], mid, r, pur);
ls[w] = max(ls[ch[w][0]], sum[ch[w][0]] + ls[ch[w][1]]);
rs[w] = max(rs[ch[w][1]], sum[ch[w][1]] + rs[ch[w][0]]);
} else {
ls[w] = rs[w] = 0;
}
} inline void insert(int p, int w, int val) {
insert(root[p],root[w],1,n,val);
}

int Get_sum(int w, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return sum[w];
} else {
int mid = l + r + 1 >> 1, ret = 0;
if (L < mid) ret += Get_sum(ch[w][0], l, mid-1, L, R);
if (mid <= R) ret += Get_sum(ch[w][1], mid, r, L, R);
return ret;
}
} inline int Get_Sum(int w, int l, int r) {
return Get_sum(root[w],1,n,l,r);
}

int query_left(int w, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return ls[w];
} else {
int mid = l + r + 1 >> 1;
if (R < mid) return query_left(ch[w][0], l, mid-1, L, R);
else if (mid <= L) return query_left(ch[w][1], mid, r, L, R);
else {
int t1 = query_left(ch[w][0], l, mid-1, L, mid-1);
int t2 = query_left(ch[w][1], mid, r, mid, R) + Get_sum(ch[w][0], l, mid-1, L, mid-1);
return max(t1, t2);
}
}
} inline int Left_Max(int w, int l, int r) {
return query_left(root[w],1,n,l,r);
}

int query_right(int w, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return rs[w];
} else {
int mid = l + r + 1 >> 1;
if (R < mid) return query_right(ch[w][0], l, mid-1, L, R);
else if (mid <= L) return query_right(ch[w][1], mid, r, L, R);
else {
int t1 = query_right(ch[w][1], mid, r, mid, R);
int t2 = query_right(ch[w][0], l, mid-1, L, mid-1) + Get_sum(ch[w][1], mid, r, mid, R);
return max(t1, t2);
}
}
} inline int Right_Max(int w, int l, int r) {
return query_right(root[w], 1, n, l, r);
}
};

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 bool judge(int sta, int *lim) {
int ret = CT::Get_Sum(sta, lim[2], lim[3]);
ret += lim[1] < lim[2] ? CT::Right_Max(sta, lim[1], lim[2] - 1) : 0;
ret += lim[3] < lim[4] ? CT::Left_Max(sta, lim[3] + 1, lim[4]) : 0;
return ret >= 0;
}

int main() {
for (int i=1;i<=n;i++)
sort(_hash+1, _hash+1+n);
tot = unique(_hash+1, _hash+1+n) - _hash - 1;
for (int i=1;i<=n;i++) {
arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
pos_que[arr[i]].push_back(i);
}
CT::init();
for (int i=2;i<=tot;i++) {
CT::insert(i-1,i,pos_que[i-1][0]);
for (int j=1,lim=pos_que[i-1].size();j<lim;j++)
CT::insert(i,i,pos_que[i-1][j]);
}

for (int i=1,lim[5],l,r,mid,ret;i<=m;i++) {
for (int j=1;j<=4;j++)
lim[j] = (read() + last_ans) % n + 1;
sort(lim+1, lim+1+4);

l = 1, r = tot;
while (l <= r) {
mid = l + r >> 1;
if (!judge(mid,lim)) r = mid-1;
else ret = mid, l = mid + 1;
}
printf("%d\n",last_ans = _hash[ret]);
}
return 0;
}


## 【BZOJ 4408】[FJOI2016] 神秘数

### 题解

ps：这货貌似是双倍经验，参见BZOJ_4299

### Code

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

const int N = 100000+9;
const int M = 3300000;
const int INF = 1e9;

int n,m,arr[N];

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],root[N];
int ans_tmp,cnt;

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

inline void insert(int p, int v) {
insert(root[p-1],root[p],1,INF,v);
}

void query(int p, int w, int l, int r, int v) {
if (l == r) {
ans_tmp += sum[w] - sum[p];
} else {
int mid = l + r + 1 >> 1;
if (v < mid) query(ch[p][0],ch[w][0],l,mid-1,v);
else {
ans_tmp += sum[ch[w][0]] - sum[ch[p][0]];
query(ch[p][1],ch[w][1],mid,r,v);
}
}
}

inline int query(int l, int r, int v) {
ans_tmp = 0;
query(root[l-1],root[r],1,INF,v);
return ans_tmp;
}
};

int main(){
for (int i=1;i<=n;i++) {
CT::insert(i,arr[i]);
}

for (int j=1,l,r,cur,tmp;j<=m;j++) {
while ((tmp = CT::query(l,r,cur+1)) > cur) {
cur = tmp;
}
printf("%d\n",cur+1);
}
return 0;
}


## 【BZOJ 2006】[NOI2010] 超级钢琴

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

const int N = 500000+9;
const int M = 20000000+9;
const int BAS = 500000010;
const int INF = 1000010000;

int n,k,L,R,arr[N];
struct Query{
int pos,num,val;
bool operator < (const Query & B) const {
return val < B.val;
}
};
priority_queue<Query> que;

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

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

inline void insert(int p, int w) {
insert(root[p-1], root[p], 1, INF, w);
}

void query(int p, int w, int l, int r, int num) {
if (l == r) ans_tmp = l;
else {
int mid = l + r + 1 >> 1;
if (sum[ch[w][1]] - sum[ch[p][1]] >= num) query(ch[p][1], ch[w][1], mid, r, num);
else query(ch[p][0], ch[w][0], l, mid-1, num - (sum[ch[w][1]] - sum[ch[p][1]]));
}
}

inline int query(int l, int r, int num) {
query(root[l-1],root[r],1,INF,num);
return ans_tmp;
}
};

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;
}

int main(){
for (int i=1;i<=n;i++) arr[i] = arr[i-1] + read();
for (int i=1;i<=n;i++) CT::insert(i,arr[i] + BAS);
for (int i=1;i+L-1<=n;i++) {
Query tmp; tmp.pos = i; tmp.num = 1;
tmp.val = CT::query(i+L-1, min(n,i+R-1), 1) - BAS - arr[i - 1];
que.push(tmp);
}

LL vout = 0;
for (int i=1,p;i<=k;i++) {
Query tmp = que.top(); que.pop();
vout += tmp.val;
if (tmp.num < R - L + 1) {
tmp.num++; p = tmp.pos;
if (n - (p+L-1) + 1 < tmp.num) continue;
tmp.val = CT::query(p+L-1, min(n,p+R-1), tmp.num) - arr[p - 1] - BAS;
que.push(tmp);
}
}
printf("%lld\n",vout);
return 0;
}


## 【NOIP十连测】[D3T3] 序列

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

const int N = 100000+9;
const int M = 10000000;

int n,m,q,arr[N];
LL last_ans;
vector<int> Q_tmp[N];

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 Segment_Tree{
#define CT Segment_Tree
int ch[M][2],sum[M],root[N],cnt,ans_tmp;

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

inline void build_tree(){
for (int i=1;i<=n;i++) {
insert(root[i-1],root[i],1,n,arr[i]);
}
}

void query(int w, int l, int r, int x, int f) {
if (!w) {
return;
} else if (l < r){
int mid = l + r + 1 >> 1;
if (mid <= x) {
query(ch[w][1],mid,r,x,f);
} else {
ans_tmp += sum[ch[w][1]]*f;
query(ch[w][0],l,mid-1,x,f);
}
} else if (l == r && l == x) {
ans_tmp += sum[w]*f;
}
}

inline int query(int l, int r, int x) {
ans_tmp = 0;
query(root[l-1],1,n,x,-1);
query(root[r],1,n,x,1);
return ans_tmp;
}

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

inline void rebuild(){
memset(ch,0,sizeof(ch));
memset(sum,0,sizeof(sum));
memset(root,0,sizeof(root));
cnt = 0;
for (int i=1;i<=n;i++) {
root[i] = root[i-1];
for (int j=0,lim=Q_tmp[i].size();j<lim;j++) {
int tmp = Q_tmp[i][j];
if (tmp < 0) {
modify(root[i],root[i],1,n,-tmp,-1);
} else {
modify(root[i],root[i],1,n,tmp,1);
}
}
}
}

void ask(int w, int l, int r, int x) {
if (!w) {
return;
} else if (l == r && r == x) {
ans_tmp += sum[w];
} else if (l < r) {
int mid = l + r + 1 >> 1;
if (x >= mid) {
ans_tmp += sum[ch[w][0]];
} else {
}
}
}

inline int requery(int p, int x) {
ans_tmp = 0;
return ans_tmp;
}
};

int main(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
for (int i=1;i<=n;i++) {
}
CT::build_tree();
for (int i=1,l,r,x;i<=m;i++) {
last_ans += CT::query(l,r,x);
Q_tmp[l].push_back(x);
Q_tmp[r+1].push_back(-x);
}
CT::rebuild();
printf("%lld\n",last_ans);
for (int T=1,a,b;T<=q;T++) {
last_ans += CT::requery(a,b);
last_ans -= CT::requery(a,arr[a]);
arr[a] = b;
printf("%lld\n",last_ans);
}
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;
}


## 【SOJ 1020】逆序对统计

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int M = 19000000;
const int N = 260000+9;

int n,m,POS[N],T;
LL vout,arr[N],NV[N],hash[N];

char c=getchar(); LL 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
#define lowbit(x) ((x)&-(x))
int ch[M][2],sz[M],root[N*2],cnt,ans_tmp;

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

inline void modify(int pos, int val, int delta){
for (int i=pos;i<=n;i+=lowbit(i))
modify(root[i],root[i],val,1,T,delta);
}

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

void query(int w, int l, int r, int L, int R) {
if (!w) return;
else if (l <= L && R <= r) ans_tmp += sz[w];
else {
int mid = L + R + 1 >> 1;
if (l < mid) query(ch[w][0],l,r,L,mid-1);
if (mid <= r) query(ch[w][1],l,r,mid,R);
}
}

inline int query(int w, int l, int r) {
ans_tmp = 0;
query(w,l,r,1,T);
return ans_tmp;
}

inline int query(int l ,int r, int L, int R){
if (l > r || L > R) return 0; int ret = 0;
for (int i=r;i;i-=lowbit(i)) ret += query(root[i],L,R);
for (int i=l-1;i;i-=lowbit(i)) ret -= query(root[i],L,R);
ret += query(root[n+r+1],L,R);
ret -= query(root[n+l-1+1],L,R);
return ret;
}
};

int main(){
sort(hash+1,hash+1+T); T = unique(hash+1,hash+1+T) - hash - 1;
for (int i=1;i<=n;i++) arr[i] = lower_bound(hash+1,hash+T+1,arr[i]) - hash;
for (int i=1;i<=m;i++) NV[i] = lower_bound(hash+1,hash+T+1,NV[i]) - hash;

CT::build();
for (int i=1;i<=n;i++) vout += CT::query(1,i-1,arr[i]+1,T);
for (int i=1,pos,nv;m;m--,i++) {
pos = POS[i]; nv = NV[i];
vout -= CT::query(1,pos-1,arr[pos]+1,T);
vout -= CT::query(pos+1,n,1,arr[pos]-1);
vout += CT::query(1,pos-1,nv+1,T);
vout += CT::query(pos+1,n,1,nv-1);
CT::modify(pos, arr[pos], -1);
CT::modify(pos, nv, 1);
arr[pos] = nv;
cout<<vout<<endl;
}
return 0;
}


## 【UOJ 218】[UNR #1] 火车管理

™我的自定义测试，那么大的数据都没有wa

std的做法是：

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 500000+9;

int n,m,ty,last_ans,arr[MAXN];

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

namespace Segment_Tree{
#define SEG Segment_Tree
const int N = MAXN*4;
int tag[N],sum[N],tm[N],ans_tmp,L,R,DEL;

inline void push_down(int w, int l, int r, int mid){
tag[w*2] = tag[w*2+1] = tag[w];
sum[w*2] = (mid-l)*arr[tag[w]];
sum[w*2+1] = (r-mid+1)*arr[tag[w]];
tag[w] = 0;
}

void query(int w, int l, int r){
if (L <= l && r <= R) ans_tmp += sum[w];
else {
int mid = (l + r + 1) / 2;
if (tag[w]) push_down(w,l,r,mid);
if (L < mid) query(w*2,l,mid-1);
if (R >= mid) query(w*2+1,mid,r);
}
}inline int query(int l, int r){ans_tmp=0;L=l,R=r;query(1,1,n);return ans_tmp;}

void Modify(int w, int l, int r){
if (L <= l && r <= R) tag[w] = DEL, sum[w] = (r-l+1)*arr[DEL];
else {
int mid = (l + r + 1) / 2;
if (tag[w]) push_down(w,l,r,mid);
if (L < mid) Modify(w*2,l,mid-1);
if (R >= mid) Modify(w*2+1,mid,r);
sum[w] = sum[w*2] + sum[w*2+1];
}
}inline void modify(int l, int r, int del){L=l,R=r,DEL=del;Modify(1,1,n);}

inline int index(int pos){
int w = 1, l = 1, r = n, mid;
while (l < r) {
if (tag[w]) return tag[w];
else {
mid = (l + r + 1) / 2;
if (pos < mid) w = w*2, r = mid-1;
else w = w*2+1, l = mid;
}
}
return tag[w];
}
};

namespace Persistent_Segment_Tree{
#define PST Persistent_Segment_Tree
const int N = 20000000;
int tag[N],root[N],ch[N][2],tot,cnt,L,R,DEL;

inline int query(int tm, int pos) {
if (tm < 1) return 0;
else {
int w = root[tm], l=1, r=n, mid;
while (l < r) {
if (tag[w]) return tag[w];
else {
mid = (l + r + 1) / 2;
if (pos < mid) w = ch[w][0], r = mid-1;
else w = ch[w][1], l = mid;
}
}
return tag[w];
}
}

inline void push_down(int w){
for (int i=0;i<=1;i++) if (!ch[w][i]) ch[w][i] = ++cnt;
for (int i=0;i<=1;i++) tag[ch[w][i]] = tag[w];
tag[w] = 0;
}

void Modify(int pre, int &w, int l, int r, int tg){
w = ++cnt; ch[w][1] = ch[pre][1];
ch[w][0] = ch[pre][0]; tag[w] = tg?tg:tag[pre];
if (L <= l && r <= R) tag[w] = DEL;
else {
int mid = (l + r + 1) / 2;
if (L < mid) Modify(ch[pre][0],ch[w][0],l,mid-1,tag[w]);
else if (tag[w]) ch[w][0] = ++cnt, tag[cnt] = tag[w];
if (mid <= R) Modify(ch[pre][1],ch[w][1],mid,r,tag[w]);
else if (tag[w]) ch[w][1] = ++cnt, tag[cnt] = tag[w];
tag[w] = 0;
}
}

inline int modify(int l, int r, int val, bool type){
L = l, R = r, DEL = val;
Modify(root[tot], root[(tot+type)], 1, n, 0);
}
};

int main(){
scanf("%d%d%d",&n,&m,&ty);
for (int i=1,type,l,r,del;i<=m;i++){
scanf("%d",&type);
if (type == 1) {
if (l > r) swap(l, r);
printf("%d\n",last_ans=SEG::query(l,r));
} else if (type == 2) {
int tmp = SEG::index(l);
int nv = PST::query(tmp-1,l);
PST::modify(l,l,nv,0);
SEG::modify(l,l,nv);
} else {