20230925 比赛总结

反思

A

感觉有点降智，一眼 $manacher$，但很久才想到可以二分，然后就转化成了一个区间最大值问题

B

感觉有点弱智的题，题目不难，一开始算复杂度的时候认为 $[1.5-3]\ast 10^8$ 冲不过 $1s$，事实上开了 $O2$ 只要 $800ms$

C

乱搞大爱！！！
但忘记 $longlong\times longlong$ 会爆！！！

题解

比赛链接

A

感觉 $manacher$ 挺显然的，因为是回文
然后的询问二分想了很久才想到，深感自己菜的本质，写代码时一些细节也调了很久

B

没什么好说的，直接 $dp$，压一下状态开冲！感觉人傻常数大，可能不加那个小剪枝就被卡常了

C

我是乱搞人！！！直接 $100pts$，我惊了！
正解是维护凸包，但我不会，先不补了

D

感觉是一道挺像暴力的数据结构
注意到 $k$ 很小，所以可以估计到 $k$ 只是用来卡常用的
所以我们考虑一组询问可以在 $O(nlogn)-O(nlo{g}^{2}n)$ 的时间复杂度内求解
考虑 $mex$ 具有可二分性，所以先二分
对于 $mid>1$ 的情况，考虑找到一条最短的路径覆盖 $0$ 到 $mid-1$ 中所有的点，如果不能，就不行，然后我们考虑从两个端点往两边拓展，然后塞到 $trie$ 树上查询有没有异或和在 $l-r$ 之间的数，这个是容易实现的
对于 $mid=1$ 的情况，我们即要找到一条路径的端点在以 $0$ 为根的两棵子树中，这个也是可以用 $trie$ 树维护的
时间复杂度 $O(knlo{g}^{2}n)$（听说 $lo{g}^2$ 被卡了，不过没事，$nfls$ 不会重测代码 ）

#include 
using namespace std;
const int N=100100;
int n,q,l,r,dis[N];
int depth[N],up[N][20];
int e[N<<1],w[N<<1],ne[N<<1],h[N],idx;
int st[N],ed[N],lim;
int ox[N],cnt;
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
int get_lca(int x,int y){
    if(depth[x]>depth[y]) swap(x,y);
    for(int i=18;i>=0;i--) if(depth[up[y][i]]>=depth[x]) y=up[y][i];
    if(x==y) return x;
    for(int i=18;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
    return up[x][0];
}
int get_dist(int x,int y){ return depth[x]+depth[y]-2*depth[get_lca(x,y)];}
void insert(int u,int fa,int xo){
	ox[++cnt]=xo;
	for(int i=h[u];~i;i=ne[i]) if(e[i]!=fa) insert(e[i],u,xo^w[i]);
}
struct Trie{
	int idx,tr[N*31][2],cnt[N*31];
	void clear(){
        for(int i=0;i<=idx;i++) tr[i][0]=tr[i][1]=cnt[i]=0;
        idx=0;
    }
	void insert(int v){
		int p=0;
		for(int i=30;i>=0;i--){
			int c=v>>i&1;
			if(!tr[p][c]) tr[p][c]=++idx;
			p=tr[p][c],cnt[p]++;
		}
	}
	int query(int v,int lim){
		if(lim<0) return 0;
		int p=0,res=0;
		for(int i=30;i>=0;i--){
			int c1=lim>>i&1,c2=v>>i&1;
			if(c1){
                res+=cnt[tr[p][c2]];
                if(!tr[p][c2^1]) return res;
                p=tr[p][c2^1];
            }
			else{
                if(!tr[p][c2]) return res;
                p=tr[p][c2];
            }
		}
		return res+cnt[p];
	}
}trie;
bool check1(int mid){//mid>1的情况
	if(mid>lim) return false;
	int S=st[mid],E=ed[mid];
	int d=get_dist(S,E),fas,fae;
	for(int i=h[S];~i;i=ne[i]) if(get_dist(e[i],E)==d-1) fas=e[i];
	for(int i=h[E];~i;i=ne[i]) if(get_dist(e[i],S)==d-1) fae=e[i];
	cnt=0,insert(S,fas,0);
	trie.clear();
	for(int i=1;i<=cnt;i++) trie.insert(ox[i]);
	cnt=0,insert(E,fae,dis[S]^dis[E]);
	for(int i=1;i<=cnt;i++) if(trie.query(ox[i],r)-trie.query(ox[i],l-1)) return true;
	return false;
}
bool check2(){
	trie.clear();
	for(int i=h[0];~i;i=ne[i]){
		cnt=0,insert(e[i],0,w[i]);
		for(int j=1;j<=cnt;j++) if(trie.query(ox[j],r)-trie.query(ox[j],l-1)) return true;
		for(int j=1;j<=cnt;j++) trie.insert(ox[j]);
	}
	return false;
}
bool insert_node(int x){
	int d1=get_dist(x,st[x-1]),d2=get_dist(x,ed[x-1]),d3=get_dist(st[x-1],ed[x-1]);
	if(d1+d2==d3) return true;
	if(d1+d3==d2){ st[x]=x;return true;}
	if(d2+d3==d1){ ed[x]=x;return true;}
	return false;
}
void dfs(int u,int fa){
    depth[u]=depth[fa]+1;
	for(int i=h[u];~i;i=ne[i]) if(e[i]!=fa) dis[e[i]]=dis[u]^w[i],up[e[i]][0]=u,dfs(e[i],u);
}
void add(int x,int y,int z){ e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;}
int main(){
    freopen("nim.in","r",stdin);
    freopen("nim.out","w",stdout);
	n=read(),q=read();
	memset(h,-1,sizeof(h));
	for(int i=1;i<n;i++){
		int x=read(),y=read(),z=read();
		add(x,y,z),add(y,x,z);
	}
	dfs(0,0);
    for(int j=1;j<=18;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];
	st[0]=ed[0]=0,st[1]=0,ed[1]=1;
	for(int i=2;i<=n;i++){
        st[i]=st[i-1],ed[i]=ed[i-1];
		if(!insert_node(i)) break;
		lim=i;
	}
	while(q--){
		l=read(),r=read();
		int lb=1,rb=n+1;
		while(lb<rb-1){
			int mid=(lb+rb)>>1;
            check1(mid-1)?lb=mid:rb=mid;
		}
        if(lb==1){
            if(check2()) puts("1");
            else puts("0");
        }
        else printf("%d\n",lb);
	}
	fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127