B是一个看起来很KDT的题 但是因为KDT是n^1.5的所以t 而且因为KDT需要周期性的重建所以复杂度会更高
因为只有51种颜色 所以想当然的就去想了状态压缩 因为询问的区间范围 x一定是从1开始的 所以可以用cdq分治
用cdq分治去掉时间维度 按x排序 用线段树维护每个区间的状态（压缩颜色） 单点更新和区间查询
因为每次线段树做cdq的一部分之后 我们都要去除影响 但是不能rebuild
1 可以用一个last代表这个区间上一次使用线段树是什么时候 每次更新和查询的时候对他进行更新
2 也可以写一个clean函数 在线段树使用结束之后 对单点更新所有经过的状态置0
3 可以单点更新 更新到叶子节点的时候将其置为0 然后递归回来 zt[ro] = zt[lson] | zt[rson] 和第二个差不多
第一个可以省去一个常数
但是其实不用cdq 因为相对还是麻烦一点
可以暴力的建立51个线段树枚举每个颜色 每个区间维护l r 区间内该颜色的最低x是多少 也是利用了查询是从1开始的特性
cdq 使用last
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
#define lro ro*2
#define rro ro*2+1
#define L long long
#define pb push_back
#define lala printf("--------\n");
#define ph push
#define rep(i, a, b) for (L i=a;i<=b;++i)
#define dow(i, b, a) for (L i=b;i>=a;--i)
#define fmt(i,n) if(i==n)printf("\n");else printf(" ") ;
#define fi first
#define se second
template<class T> inline void flc(T &A, L x){memset(A, x, sizeof(A));}
L read(){L x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
struct node {
L x,y,c;
L y2;
L xw ;
L time ;
node(L xx,L yy,L cc,L y22,L ww,L tt) : x(xx) , y (yy) , c(cc) , y2(y22) , xw(ww) , time(tt) {}
node() {}
};
L ans[300050] ;
vector<node>q1 , q2 ;
L tot ;
struct tre {
L last ;
L zt ;
}t[1000050 * 6];
void build(L ro , L l , L r) {
t[ro].zt = 0 ;
if(l == r) return ;
L mid = (l + r) >> 1 ;
build(lro , l , mid) ; build(rro , mid+1 , r) ;
}
void upda(L ro , L l , L r , L id , L val , L pos) {
if(t[ro].last != id) {
t[ro].last = id ;
t[ro].zt = 0 ;
}
t[ro].zt |= (1LL << val) ;
L mid = (l + r) >> 1 ;
if(l == r) return ;
if(pos <= mid) upda(lro , l , mid , id , val , pos) ;
else upda(rro , mid+1 , r , id , val , pos) ;
}
void query(L ro, L l , L r , L id , L ql , L qr , L ansid) {
if(t[ro].last != id) return ;
if(l >= ql && r <= qr) {
ans[ansid] |= t[ro].zt ;
return ;
}
if(l == r) return ;
L mid = (l + r) >> 1 ;
if(ql <= mid) query(lro , l , mid , id , ql , qr , ansid) ;
if(qr > mid) query(rro , mid+1 , r , id, ql , qr , ansid) ;
}
void cdq2(L LL , L RR) {
tot ++ ;
rep(i , LL , RR) {
if(q2[i].xw == 0) {
upda(1,1,1000000,tot,q2[i].c,q2[i].y) ;
}
else {
query(1,1,1000000,tot,q2[i].y,q2[i].y2,q2[i].time) ;
}
}
}
bool cmp(node a,node b) {
if(a.x==b.x) return a.time < b.time ;
return a.x < b.x ;
}
void cdq(L LL , L RR) {
if(RR <= LL) return ;
L M = (LL + RR) >> 1 ;
cdq(LL,M) ;
q2.clear();
rep(i,LL,M) {
if(q1[i].xw == 0) q2.pb(q1[i]) ;
}
rep(i,M+1,RR) {
if(q1[i].xw == 1) q2.pb(q1[i]) ;
}
sort(q2.begin(),q2.end(),cmp) ;
int siz = q2.size() ;
cdq2(0,siz-1);
cdq(M+1,RR) ;
}
L zh(L x) {
L res = 0 ;
while(x) {
if(x&1) res ++ ;
x>>=1 ;
}
return res ;
}
int main () {
tot = 0 ;
// freopen("6183.txt" , "r" , stdin) ;
L op ;
q1.clear() ;
while(scanf("%lld" , &op) != EOF) {
if(op == 0) {
build(1,1,1000000) ;
int siz = q1.size() ;
cdq(0,siz-1);
for(L i=0;i<siz;i++ ){
if(ans[i] >= 0) printf("%lld\n" , zh(ans[i])) ;
}
q1.clear();
flc(ans,0) ;
}
else if(op == 3) {
build(1,1,1000000) ;
int siz = q1.size() ;
cdq(0,siz-1);
for(L i=0;i<siz;i++ ){
if(ans[i] >= 0) printf("%lld\n" , zh(ans[i])) ;
}
q1.clear();
flc(ans,0) ;
return 0;
}
else if(op == 1) {
L x=read() ;
L y=read() ;
L c=read() ;
int siz = q1.size() ;
ans[siz] = -1 ;
q1.pb(node(x,y,c,0,0,siz)) ;
}
else if(op == 2) {
L x=read() ;
L y=read() ;
L y2=read() ;
int siz = q1.size() ;
q1.pb(node(x,y,0,y2,1,siz)) ;
}
}
}
cdq 使用clean
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
#define lro ro*2
#define rro ro*2+1
#define L long long
#define pb push_back
#define lala printf("--------\n");
#define ph push
#define rep(i, a, b) for (L i=a;i<=b;++i)
#define dow(i, b, a) for (L i=b;i>=a;--i)
#define fmt(i,n) if(i==n)printf("\n");else printf(" ") ;
#define fi first
#define se second
template<class T> inline void flc(T &A, L x){memset(A, x, sizeof(A));}
L read(){L x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
struct node {
L x,y,c;
L y2;
L xw ;
L time ;
node(L xx,L yy,L cc,L y22,L ww,L tt) : x(xx) , y (yy) , c(cc) , y2(y22) , xw(ww) , time(tt) {}
node() {}
};
L ans[300050 * 2] ;
vector<node>q1 , q2 ;
L zt[1000050 * 10] ;
void build(L ro , L l , L r) {
zt[ro] = 0 ;
if(l == r) return ;
L mid = (l + r) >> 1 ;
build(lro , l , mid) ; build(rro , mid+1 , r) ;
}
void upda(L ro , L l , L r , L val , L pos) {
zt[ro] |= (1LL << val) ;
if(l == r) return ;
L mid = (l + r) >> 1 ;
if(pos <= mid) upda(lro , l , mid , val , pos) ;
else upda(rro , mid+1 , r , val , pos) ;
}
void query(L ro, L l , L r , L ql , L qr , L ansid) {
if(l >= ql && r <= qr) {
ans[ansid] |= zt[ro] ;
return ;
}
if(l == r) return ;
L mid = (l + r) >> 1 ;
if(ql <= mid) query(lro , l , mid , ql , qr , ansid) ;
if(qr > mid) query(rro , mid+1 , r , ql , qr , ansid) ;
}
void clean(L ro , L l , L r , L pos) {
zt[ro] = 0 ;
if(l == r) return ;
L mid = (l + r) >> 1 ;
if(pos <= mid) clean(lro , l , mid , pos) ;
else clean(rro , mid+1 , r , pos) ;
}
void cdq2(L LL , L RR) {
rep(i , LL , RR) {
if(q2[i].xw == 0) {
upda(1,1,1000000,q2[i].c,q2[i].y) ;
}
else {
query(1,1,1000000,q2[i].y,q2[i].y2,q2[i].time) ;
}
}
rep(i , LL , RR) {
if(q2[i].xw == 0) {
clean(1,1,1000000,q2[i].y) ;
}
}
}
bool cmp(node a,node b) {
if(a.x==b.x) return a.time < b.time ;
return a.x < b.x ;
}
void cdq(L LL , L RR) {
if(RR <= LL) return ;
L M = (LL + RR) >> 1 ;
cdq(LL,M) ;
q2.clear();
rep(i,LL,M) {
if(q1[i].xw == 0) q2.pb(q1[i]) ;
}
rep(i,M+1,RR) {
if(q1[i].xw == 1) q2.pb(q1[i]) ;
}
sort(q2.begin(),q2.end(),cmp) ;
L siz = q2.size() ;
cdq2(0,siz-1);
cdq(M+1,RR) ;
}
L zh(L x) {
L res = 0 ;
while(x) {
if(x%2 == 1) res ++ ;
x /= 2 ;
}
return res ;
}
int is[300050] ;
int main () {
//freopen("6183.txt" , "r" , stdin) ;
L op ;
flc(ans , 0) ;
q1.clear() ;
while(scanf("%lld" , &op) != EOF) {
if(op == 0) {
build(1,1,1000000) ;
L siz = q1.size() ;
cdq(0,siz-1);
for(L i=0;i<siz;i++ ){
if(is[i]) printf("%lld\n" , zh(ans[i])) ;
}
q1.clear();
flc(ans,0) ;
}
else if(op == 3) {
build(1,1,1000000) ;
L siz = q1.size() ;
cdq(0,siz-1);
for(L i=0;i<siz;i++ ){
if(is[i]) printf("%lld\n" , zh(ans[i])) ;
}
q1.clear();
flc(ans,0) ;
return 0;
}
else if(op == 1) {
L x=read() ;
L y=read() ;
L c=read() ;
L siz = q1.size() ;
ans[siz] = -32000 ;
is[siz] = 0 ;
q1.pb(node(x,y,c,0,0,siz)) ;
}
else if(op == 2) {
L x=read() ;
L y=read() ;
L y2=read() ;
L siz = q1.size() ;
ans[siz] = 0 ;
is[siz] = 1 ;
q1.pb(node(x,y,0,y2,1,siz)) ;
}
}
}
51个线段树 需要动态的建点 用到哪个点再去建它 省空间
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
#define L long long
#define pb push_back
#define ph push
#define lala printf(" --------- \n") ;
#define rep(i, a, b) for (int i=a;i<=b;++i)
#define dow(i, b, a) for (int i=b;i>=a;--i)
#define fmt(i,n) if(i==n)printf("\n");else printf(" ") ;
#define lro ro*2
#define rro ro*2+1
#define fi first
#define se second
template<class T> inline void flc(T &A, int x){memset(A, x, sizeof(A));}
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int op ;
int ls[50 * 500000 * 4] ;
int rs[50 * 500000 * 4] ;
int mi[50 * 500000 * 4] ;
int root[70] ;
int cnt ;
void init() {
rep(i,0,cnt) {
root[i] = ls[i] = rs[i] = 0 ;
}
cnt = 0 ;
}
void upda(int & x , int l , int r , int pos , int val) {
if(x == 0) {
x = ++cnt ;
mi[x] = 10000000 ;
}
mi[x] = min(mi[x] , val) ;
if(l == r) return ;
int mid = (l + r) / 2 ;
if(pos <= mid) {
upda(ls[x] , l , mid , pos , val) ;
}
else {
upda(rs[x] , mid+1 , r , pos , val) ;
}
}
int ok ;
void query(int x , int l , int r , int ql , int qr , int fz) {
if(ok || x == 0) return ;
if(ql <= l && qr >= r) {
if(mi[x] <= fz) ok = 1 ;
return ;
}
int mid = (l + r) / 2 ;
if(ql <= mid) query(ls[x] , l , mid , ql , qr , fz) ;
if(qr > mid) query(rs[x] , mid+1 , r , ql , qr , fz) ;
}
int main () {
while(scanf("%d" , &op) != EOF){
if(op == 3) return 0 ;
if(op == 0) {
init() ;
}
if(op == 1) {
int x = read() ; int y = read() ; int c = read() ;
upda(root[c] , 1 , 1000000 , y , x) ;
}
if(op == 2) {
int x = read() ;
int y1 = read() ; int y2 = read() ;
int ans = 0 ;
rep(i,0,50) {
ok = 0 ;
query(root[i] , 1 , 1000000 , y1 , y2 , x) ;
if(ok) ans ++ ;
}
printf("%d\n" , ans) ;
}
}
}
K的xor让人一看就觉得是字典树 但是正常肯定没法做 想到类似主席树一样 用dfs序把每个子树分成区间 就可以写出一个挺像主席树的可持久化字典树了
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
#define L long long
#define pb push_back
#define ph push
#define lala printf(" --------- \n") ;
#define rep(i, a, b) for (L i=a;i<=b;++i)
#define dow(i, b, a) for (L i=b;i>=a;--i)
#define fmt(i,n) if(i==n)printf("\n");else printf(" ") ;
#define lro ro*2
#define rro ro*2+1
#define fi first
#define se second
template<class T> inline void flc(T &A, L x){memset(A, x, sizeof(A));}
L read(){L x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
struct node {
L l , r , sum ;
}b[5000050];
node newnode() {
node a;
a.l = a.r = -1 ;
a.sum = 0 ;
return a ;
}
L n , q ;
L a[100050] ;
L root[100050] ;
struct ed {
L v , nex ;
}bb[200050] ;
L head[100050] ;
L cnt ;
void add(L u,L v) {
cnt ++ ;
bb[cnt].v=v;bb[cnt].nex=head[u];head[u]=cnt;
}
L l[100050] ;
L r[100050] ;
L num ;
L p[100050] ;
void dfs(L u , L fa) {
num ++ ;
l[u] = num ;
p[num] = u ;
for(L i = head[u] ; i != -1 ; i = bb[i].nex) {
L v = bb[i].v ;
if(v == fa) continue ;
dfs(v,u) ;
}
r[u] = num ;
}
L tot ;
L c[35] ;
void fj(L x) {
rep(i,1,33) {
c[i] = x % 2 ;
x /= 2 ;
}
}
void inse1(L w , L val ) {
fj(w) ;
L ro = 0 ;
dow(i,33,1) {
if(c[i] == 1) {
if(b[ro].r == -1) {
b[ro].r = ++cnt ;
b[cnt] = newnode() ;
}
ro = b[ro].r ;
b[ro].sum += val ;
}
else {
if(b[ro].l == -1) {
b[ro].l = ++cnt ;
b[cnt] = newnode() ;
}
ro = b[ro].l ;
b[ro].sum += val ;
}
}
}
void inse(L w , L id , L y) {
fj(w) ;
tot ++ ;
root[id] = tot ;
L ro = tot ;
b[ro] = b[y] ;
b[ro].sum ++ ;
dow(i,33,1) {
if(c[i] == 1) {
b[ro].r = ++cnt ;
ro = b[ro].r ;
y = b[y].r ;
b[ro] = b[y] ;
b[ro].sum ++ ;
}
else{
b[ro].l = ++cnt ;
ro = b[ro].l ;
y = b[y].l ;
b[ro] = b[y] ;
b[ro].sum ++ ;
}
}
}
L sd[50] ;
L query(L l , L r , L x) {
fj(x) ;
L res = 0 ;
L rol = root[l-1] ;
L ror = root[r] ;
dow(i,33,1) {
if(c[i] == 1) {
if(b[b[ror].l].sum - b[b[rol].l].sum > 0) {
rol = b[rol].l ;
ror = b[ror].l ;
res += sd[i] ;
}
else {
rol = b[rol].r ;
ror = b[ror].r ;
}
}
else {
if(b[b[ror].r].sum - b[b[rol].r].sum > 0) {
rol = b[rol].r ;
ror = b[ror].r ;
res += sd[i] ;
}
else {
rol = b[rol].l ;
ror = b[ror].l ;
}
}
}
return res ;
}
int main () {
sd[1] = 1LL ;
rep(i , 2 , 33) {
sd[i] = sd[i-1] * 2LL ;
}
while(scanf("%lld" , &n) != EOF) {
flc(head,-1);
cnt = 0 ;
b[0] = newnode() ;
root[0] = 0 ;
tot = 0 ;
q = read() ;
rep(i,1,n) {
a[i]=read();
}
rep(i,2,n) {
L fa=read();
add(fa,i) ;
add(i,fa) ;
}
num = 0 ;
dfs(1 , -1) ;
rep(i,1,n) {
inse1(a[i] , 1) ;
inse1(a[i] , -1) ;
}
rep(i,1,n) {
inse(a[p[i]] , i , root[i-1]) ;
}
while(q -- ) {
L u , x ;
u = read();
x = read();
L ans = query(l[u] , r[u] , x) ;
printf("%lld\n" , ans) ;
}
}
}