一些废话
n个树，其实是有n个线段树
每个线段树记录前n个数插入的状态，是把整个序列排序之后插入自己该在的位置（类似于树状数组求逆序对的那种插入姿势）
每次新建一个线段树大部分节点都是从前一棵树上掰下来的，公用的，所以每次增加nlogn个节点
poj2104
拿去年的板子改的，去年的代码好丑，换成舒服的风格
# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
using namespace std;
const int N = 1e5 + 7;
int arr[N]; //arr[] 原数组的数在rank[]中的位置;
int Rank[N]; //rank[] 原数组离散化
struct ChairTree{
#define sum(x) tree[x].w
#define lson tree[rt].lc, tree[rt1].lc, l, m
#define rson tree[rt].rc, tree[rt1].rc, m+1, r
struct node{
int lc, rc, w;
node(){}
} tree[N * 20];
int root[N], cnt;
void build(){
root[0] = cnt = 0;
memset(tree, 0, sizeof(tree));
}
void add(int pos, int val, int &rt, int rt1, int l, int r){
tree[rt = ++cnt] = tree[rt1];
tree[rt].w += val;
if (l == r) return;
int m = (l + r) >> 1;
if (pos <= m) add(pos, val, lson);
else add(pos, val, rson);
}
int query(int k, int rt, int rt1, int l, int r){
if (l == r) return l;
int lsize = sum(tree[rt1].lc) - sum(tree[rt].lc);
int m = (l + r) >> 1;
if (lsize >= k) return query(k, lson);
else return query(k - lsize, rson);
}
} T;
int main(){
//freopen("in.txt","r",stdin);
int _, l, r, k, n, q;
for (; ~scanf("%d%d", &n, &q);){
T.build();
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
Rank[i] = arr[i];
}
sort(Rank + 1, Rank + n+1);//Rank存储原值
int m = unique(Rank + 1, Rank + n +1) - (Rank + 1);
for (int i = 1; i <= n; i++) {//离散化后的数组，仅仅用来更新
arr[i] = lower_bound(Rank + 1, Rank + n+1, arr[i]) - Rank;
}
for (int i = 1; i <= n; i++){
T.add(arr[i], 1, T.root[i], T.root[i-1], 1, n);
}
for (; q--;){
scanf("%d%d%d", &l, &r, &k);
int pos = T.query(k, T.root[l-1], T.root[r], 1, n);
printf("%d
", Rank[pos]);
}
}
return 0;
}
EOJ3335&&hdu6162
多校第九场02
本题花式A法可以看这里
树上套个主席树
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
typedef long long LL;
LL gift[N], Rank[N];//节点权值和离散化
struct ChairTree{
#define sum(x) tree[x].sum
#define lson tree[rt].lc, tree[rt1].lc, l, m
#define rson tree[rt].rc, tree[rt1].rc, m+1, r
struct node{
int lc, rc;
LL sum;
} tree[N * 30];
int n, root[N], cnt;
inline void build(int _n){
n = _n; cnt = 0;
}
void add(int pos, LL val, int &rt, int rt1, int l, int r){
tree[rt = ++cnt] = tree[rt1];
tree[rt].sum += val;
if (l == r) return;
int m = (l + r) >> 1;
if (pos <= m) add(pos, val, lson);
else add(pos, val, rson);
}
LL query(int L, int R, int rt, int rt1, int l, int r){
if (L <= l && r <= R) return sum(rt1) - sum(rt);
if (sum(rt1) == 0) return 0;
if (sum(rt1) == sum(rt)) return 0;
LL ans = 0;
int m = (l + r) >> 1;
if (L <= m) ans += query(L, R, lson);
if (m < R) ans += query(L, R, rson);
return ans;
}
#undef sum(x)
#undef lson
#undef rson
} T;
struct graph{
struct Edge{
int from, to, nxt;
Edge(){}
Edge(int u, int v, int n):from(u), to(v), nxt(n){}
} edges[N * 2];
static const int LCADEP = 17;
int n, E, head[N];
int top, dep[N], fa[N][LCADEP + 1];
inline void AddEdge(int f, int t){
edges[++E] = Edge(f, t, head[f]);
head[f] = E;
}
inline void Init(int n){
this -> n = n ; E = -1; top = 0; dep[0] = 0;
for (int i = 0; i <= n; i++) head[i] = -1;
memset(fa, 0, sizeof(fa));
}
void dfs(int u, int pre){
T.add(gift[u], Rank[gift[u]], T.root[u], T.root[pre], 1, T.n);
fa[u][0] = pre;
dep[u] = dep[pre] + 1;
for (int i = 1; i <= LCADEP; i++){
if (dep[u] < (1<<i)) break;
fa[u][i] = fa[fa[u][i-1]][i-1];
}
for (int i = head[u]; i != -1; i = edges[i].nxt){
if (edges[i].to != pre) dfs(edges[i].to, u);
}
}
int lca(int x, int y){
if (dep[x] < dep[y]) swap(x,y);
int t = dep[x] - dep[y];
for (int i = 0; i <= LCADEP; i++) if ((1<<i) & t) x = fa[x][i];
for (int i = LCADEP; i >= 0; i--) if (fa[x][i] != fa[y][i]){
x = fa[x][i]; y = fa[y][i];
}
return x==y ? x : fa[x][0];
}
LL query(int u, int v, int L, int R){
int f = lca(u, v);
LL ans = 0;
ans += T.query(L, R, T.root[f], T.root[u], 1, T.n);
ans += T.query(L, R, T.root[fa[f][0]], T.root[v], 1, T.n);
return ans;
}
} g ;
int main () {
//freopen("in.txt", "r", stdin);
int n, q, u, v;
for (LL a, b; ~scanf("%d%d", &n, &q);) {
for(int i = 1; i <= n; i++) {
scanf("%lld", &gift[i]);
Rank[i] = gift[i];
}
sort(Rank + 1, Rank + n+1);
int un = unique(Rank + 1, Rank + n+1) - (Rank+1);
for (int i = 1; i <= n; i++){
gift[i] = lower_bound(Rank + 1, Rank + un+1, gift[i]) - Rank;
}
g.Init(n);
for(int i = 0; i < n - 1; i++) {
scanf("%d%d", &u, &v);
g.AddEdge(u, v);
g.AddEdge(v, u);
}
T.build(un);
g.dfs(1, 0);
for (; q--;){
scanf("%d%d%lld%lld", &u, &v, &a, &b);
int aa = lower_bound(Rank+1, Rank + un+1, a) - Rank;
if (Rank[aa] < a) aa++;
int bb = lower_bound(Rank+1, Rank + un+1, b) - Rank;
if (bb > un || Rank[bb] > b) bb--;
printf("%lld", g.query(u, v, aa, bb));
putchar(q==0 ? '
' : ' ');
}
}
return 0;
}
hdu5919
看了这个题解写的
题意
有长度为n的序列，强制在线询问[l,r] 这段区间中所有不同数出现的第一个位置，按照位置从小到大排完序以后的中间（向上取整）的那个位置是多少？
真-语文题
解
没有对原来数据的离散化操作，每棵线段树就是原数组的位置
每个数字只有一次，每次+1，前面有了就吧前面的-1
for的时候最坏要update 2*n次，所以要开40*n的大小
# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
using namespace std;
const int N = 2e5 + 7;
int n, arr[N], last[N];
struct ChairTree{
#define lson tree[rt].lc, tree[rt1].lc, l, m
#define rson tree[rt].rc, tree[rt1].rc, m+1, r
struct node{
int lc, rc, w;
node(){}
} tree[N * 40];
int root[N], cnt;
inline void build(){
root[0] = root[n+1] = cnt = 0;
memset(tree, 0, sizeof(tree));
memset(root, 0, sizeof(root));
}
void add(int pos, int val, int &rt, int rt1, int l, int r){
int tmp = rt;
tree[rt = ++cnt] = tmp ? tree[tmp] : tree[rt1];
tree[rt].w += val;
if (l == r) return;
int m = (l + r) >> 1;
if (pos <= m) add(pos, val, lson);
else add(pos, val, rson);
}
//下面两个函数, rt==rt1, 带两个仅仅是为了凑个lson和rson的参数
int sum(int L, int R, int rt, int rt1, int l, int r){
if (L <= l && r <= R) return tree[rt].w;
int ans = 0;
int m = (l + r) >> 1;
if (L <= m) ans += sum(L, R, lson);
if (m < R) ans += sum(L, R, rson);
return ans;
}
int query(int k, int rt, int rt1, int l, int r){
if (l == r) return l;
int lsize = tree[tree[rt].lc].w;
int m = (l + r) >> 1;
if (lsize >= k) return query(k, lson);
else return query(k - lsize, rson);
}
} T;
int main(){
//freopen("in.txt","r",stdin);
int _, __, l, r, q;
scanf("%d", &__);
for (int _ = 1; _ <= __; _++){
printf("Case #%d:", _);
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
T.build();
memset(last, 0, sizeof(last));
for (int i = n; i >= 1; i--){
T.add(i, 1, T.root[i], T.root[i+1], 1, n);
if (last[arr[i]]) T.add(last[arr[i]], -1, T.root[i], T.root[i], 1, n);
last[arr[i]] = i;
}
int ans = 0;
for (; q--;){
scanf("%d%d", &l, &r);
l = (l + ans) % n + 1;
r = (r + ans) % n + 1;
if (l > r) swap(l, r);
int sum = T.sum(l, r, T.root[l], T.root[l], 1, n);
ans = T.query((sum+1)/2, T.root[l], T.root[l], 1, n);
printf(" %d", ans);
}
puts("");
}
return 0;
}