P5648 Mivik的神力

神！ deco\color{black}{\text{d}}\color{red}{\text{eco}} 神

原来的题意就是问 ∑i=lrRMQ(l,i)\sum\limits_{i=l}^{r}{\text{RMQ}(l,i)}

强制在线

拿到题的网友直呼不可做，分析也没分析啥，但是考虑一个点要作为[l,i][l,i] 的RMQ的话说明左边都比它小，也就是最大的比他小，然后这样就可以牵出一条链，根据性质还可以进一步推出这是一颗树！

然后怎么办，统计[l,r][l,r] 的答案 [l,i][l,i] 的 ansans 就是 ll 牵出来到 ii 的一条链中最大的节点，这样可以拿 $ 90$ 分

再考虑性质，发现上面那部分可以倍增来做

原题时限0.1s，下面的做法常数大了

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=500500;

int f[maxn][20],ans[maxn][20];
int n,m,_log2[maxn];
int a[maxn],sz[maxn];
stack <int> s;

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	int lasl=1;
	_log2[0]=-1;
	for(i=1;i<=n;i++)
	{
		cin>>a[i]; _log2[i]=_log2[i>>1]+1;
		while(!s.empty()&&a[i]>a[s.top()]) f[s.top()][0]=i,sz[s.top()]=i-s.top(),s.pop();
		s.push(i); 
	}
	while(!s.empty()) f[s.top()][0]=n+1,sz[s.top()]=n+1-s.top(),s.pop();
	for(i=1;i<=n;i++) ans[i][0]=sz[i]*a[i];
	for(j=1;(1<<j)<=n;j++) for(i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1],ans[i][j]=ans[i][j-1]+ans[f[i][j-1]][j-1];
	int l,r,lasans=0,tans=0;
	for(i=1;i<=m;i++)
	{
		cin>>l>>r;
		l=1+(l^lasans)%n,r=1+(r^(lasans+1))%(n-l+1);
		int pla=l; r=l+r-1;
		tans=0;
		for(j=_log2[r-l+1];j>=0&&pla<=r;j--)
		{
			if(f[pla][j]&&f[pla][j]<=r) tans+=ans[pla][j],pla=f[pla][j]; 
		}
		tans+=a[pla]*(r-pla+1);		
		cout<<tans<<endl;
		lasans=tans;
	}
	return 0;
}

P3765 总统选举

lxl\text{lxl} 说过，既然出现了一次，那么每次我们都有12\frac{1}{2} 的概率选到那个数，这里多选几次基本就可以了，然后判断是不是超过了一半，时间复杂度大概在 O(nlog⁡2n)O(n\log^2n)

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define ls(i) t[i].ls
#define rs(i) t[i].rs

using namespace std;

const int maxn=501000;

int a[maxn],n,m,_log2[maxn];
int vis[maxn];

int rdst=13173,p1=8848;

int rd()
{
	rdst=(1ll*rdst*p1)%(1ll*(1ll<<30)-1);
	return rdst;
}

int tot;

vector <int> v[maxn];

int getsz(int x,int ll,int rr)
{
	int l,r;
	if(v[x].empty()) return 0;
	l=lower_bound(v[x].begin(),v[x].end(),ll)-v[x].begin();
	r=lower_bound(v[x].begin(),v[x].end(),rr+1)-v[x].begin();
	return r-l;
}

int getans(int l,int r,int s,int k)
{
	int i,j;
	for(i=1;i<=n;i++) printf("%d ",a[i]); printf("\n");
	int looker=max(100,_log2[r-l+1]+1);
	int pus=1;
	for(i=1;i<=looker;i++) 
	{
		int x=rd()%(r-l+1)+l;
		if(getsz(a[x],l,r)>(r-l+1)/2) return a[x];
	}
	return s;
}

int main()
{
	register int i,j;
	//cin>>n>>m;
	scanf("%d %d",&n,&m);
	int tmp,t1;
	_log2[0]=-1;
	for(i=1;i<=n;i++)
	{
		_log2[i]=_log2[i>>1]+1;
		scanf("%d",&a[i]);
		v[a[i]].push_back(i);
	}
	int l,r,s,k;
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d %d",&l,&r,&s,&k);
		tmp=getans(l,r,s,k);
		printf("%d\n",tmp);
		for(j=1;j<=k;j++) 
		{
			scanf("%d",&t1);
			v[a[t1]].erase(lower_bound(v[a[t1]].begin(),v[a[t1]].end(),t1));
			v[tmp].insert(lower_bound(v[tmp].begin(),v[tmp].end(),t1),t1);
			a[t1]=tmp;
		}
	}
	int ans=-1;
	for(i=1;i<=n;i++) 
	{
		vis[a[i]]++;
		if(vis[a[i]]>(n+1)/2) ans=a[i];
	}
	printf("%d\n",ans);
	return 0;
}

//			if(l==r) return a[l];
//			int x=rd()%(r-l+1)+l;
//			vis[a[x]]++;
//			tmp[++cnt]=a[x];
//			if(vis[a[x]]>vis[mmx]&&mmx!=a[x]) mmx2=mmx,mmx=a[x];
//			else if(vis[a[x]]>vis[mmx2]&&mmx2!=a[x]&&mmx!=a[x]) mmx2=a[x];
//			if(vis[a[x]]>=looker/2-pus&&vis[mmx]-vis[mmx2]>=pus)
//			{
//				for(j=1;j<=cnt;j++) vis[tmp[j]]--;
//				return a[x];
//			}
	//for(int k=0;k<v[a[t1]].size();k++) cout<<v[a[t1]][k]<<" ";
			//cout<<endl;

P3674 小清新人渣的本愿

其实是个莫队，用 bitset\text{bitset} 的地方很巧妙

考虑如何处理相差为 xx ，将所有数字的 bitset\text{bitset} 移 xx 位即可

考虑处理和为 xx ,记录一个 bitset\text{bitset} 为 maxn−a[i]maxn-a[i] 然后数字的 $ \text{bitset}$ 和这个数组左移 xx 位 &\& 一下

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<bitset>

using namespace std;

const int maxn=100100;
const int loopn=1e5;

bitset <maxn> ci,cd,tmp;

int looker[maxn];
int n,m,a[maxn],ans[maxn];
int bl[maxn],len;
int lk[]={-1,1};

struct que{
	int l,r,x,bh,opt;
	bool operator <(const que &b)
	const {
		if(bl[l]==bl[b.l]) return lk[bl[l]&1]*r<lk[bl[l]&1]*b.r;
		return bl[l]<bl[b.l];
	}
}q[maxn];

inline void add(int x)
{
	looker[a[x]]++; if(looker[a[x]]==1) ci[a[x]]=1,cd[loopn-a[x]]=1;
}

inline void del(int x)
{
	looker[a[x]]--; if(looker[a[x]]==0) ci[a[x]]=0,cd[loopn-a[x]]=0;
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	scanf("%d %d",&n,&m);
	len=sqrt(n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]),bl[i]=(i-1)/len+1;
	for(i=1;i<=m;i++) scanf("%d %d %d %d",&q[i].opt,&q[i].l,&q[i].r,&q[i].x),q[i].bh=i;
	sort(q+1,q+m+1);
	int l=1,r=0;
	for(i=1;i<=m;i++)
	{
		while(r<q[i].r) add(++r);
		while(l>q[i].l) add(--l);
		while(r>q[i].r) del(r--);
		while(l<q[i].l) del(l++);
		if(q[i].opt==1)
		{
			tmp=ci&(ci<<q[i].x);
			ans[q[i].bh]=tmp.any();
		}
		if(q[i].opt==2)
		{
			tmp=cd&(ci<<(loopn-q[i].x));
			ans[q[i].bh]=tmp.any();
		}
		if(q[i].opt==3)
		{
			int j;
			for(j=1;j*j<=q[i].x;j++) 
			{
				if(q[i].x%j!=0) continue;
				if(ci[j]&&ci[q[i].x/j])
				{
					ans[q[i].bh]=1;
					break;
				}
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		if(ans[i]==1) printf("hana\n");
		else printf("bi\n");
	}
	return 0;
}

P2114 [NOI2014]起床困难综合症

也是一个bitset，并且分组处理询问，注意一下细节就能AC

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<bitset>

using namespace std;

const int maxn=100200;

int lk[]={-1,1};
int a[maxn],b[maxn],n,m;
const int quelen=3e4;

bitset <maxn> looker[quelen+20],c,tmp;

int ans[maxn];
int bl[maxn],len,cnt=0;
int sz[maxn],ls[maxn];

map <int,int> mp;

struct que{
	int l,r,bh;
	bool operator <(const que &bb)
	const {
		if(bl[l]==bl[bb.l]) return (lk[bl[l]&1])*r<(lk[bl[bb.l]&1])*bb.r;
		return l<bb.l; 
	}
}q[maxn];

inline void add(int x){c[a[x]+(++sz[a[x]])-1]=1;}
inline void del(int x){c[a[x]+(sz[a[x]])-1]=0; sz[a[x]]--;}

void getans(int tm)
{
	int i,j;
	c.reset();
	memset(sz,0,sizeof(sz));
	int lkrt=0;
	tm=min(tm,m-cnt/3);
	if(!tm) return ;
	int mu=0;
	for(i=1;i<=tm;i++) 
	{
		mu++; cin>>q[mu].l>>q[mu].r; q[mu].bh=i; cnt++; ls[mu]=q[mu].r-q[mu].l+1;
		mu++; cin>>q[mu].l>>q[mu].r; q[mu].bh=i; cnt++; ls[mu]=q[mu].r-q[mu].l+1;
		mu++; cin>>q[mu].l>>q[mu].r; q[mu].bh=i; cnt++; ls[mu]=q[mu].r-q[mu].l+1;
		looker[i].set();
	}
	tm*=3;
	sort(q+1,q+tm+1);
	int l=1,r=0;
	for(i=1;i<=tm;i++)
	{
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(l<q[i].l) del(l++);
		while(r>q[i].r) del(r--);
		looker[q[i].bh]&=c;
	}
	tm/=3;
	for(i=1;i<=tm;i++)
	{
		cout<<(ls[i*3-2]+ls[i*3-1]+ls[i*3]-3*looker[i].count())<<endl;
	}
	return ;
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	len=sqrt(n); 
	for(i=1;i<=n;i++) cin>>a[i],b[i]=a[i],bl[i]=(i-1)/len+1;
	sort(b+1,b+n+1);
	//int tot=unique(b+1,b+n+1)-b-1;
	int tot=n;
	for(i=1;i<=n;i++) a[i]=lower_bound(b+1,b+tot+1,a[i])-b; 
	//for(i=1;i<=n;i++) cout<<a[i]<<" ";
	getans(quelen);
	getans(quelen);
	getans(quelen);
	getans(quelen);
	return 0;
}

P1099 树网的核/P2491 [SDOI2011]消防

给你一棵树，让你找到长度不超过 kk 的路径满足 距离这个路径最远的点距离最小

首先不难发现，这条路径一定在直径上，显然地我们可以证明，如果不在直径上，那么距离它最远的点一定在直径上而且一定更长。

因此我们找到直径序列，用一个尺取法，然后记录 ll 左边的直径上的点到 ll 的最大值，以及 rr 右边的直径上的点到 rr 的最大值，再到这个序列的点的最大值即可

听起来很麻烦对不对 ，实际上面三个都可以 O(N)O(N) 实现

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=300300;

int n,m,head[maxn],size;
int diameter[maxn];
int dis[maxn],mmx;
int vis[maxn];
int f[maxn];
int looker[maxn],cnt,ans=0x3f3f3f3f;
int lasdis[maxn];
int st,ed;
int lx[maxn],rx[maxn],dsum[maxn];
int q[maxn],ll=1,rr;

struct edge{
	int next,to,dis;
}e[maxn*2];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

void dfs1(int t,int fat)
{
	int i,j,k;
	f[t]=fat;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		k=e[i].dis;
		if(j==fat) continue;
		dis[j]=dis[t]+k;
		lasdis[j]=k;
		dfs1(j,t);
		if(dis[j]>dis[mmx]) mmx=j;
	}
}

void dfs2(int t,int fat)
{
	int i,j,k;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		k=e[i].dis;
		if(j==fat) continue;
		dfs2(j,t);
		dis[t]=max(dis[j]+k,dis[t]);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	int t1,t2,t3;
	for(i=1;i<n;i++) cin>>t1>>t2>>t3,addedge(t1,t2,t3),addedge(t2,t1,t3);
	dfs1(1,0);
	memset(dis,0,sizeof(dis)); st=mmx;
	memset(lasdis,0,sizeof(lasdis)); 
	memset(f,0,sizeof(f));
	dfs1(mmx,0);
	ed=mmx;
	int p=ed;
	while(p) 
	{
		looker[++cnt]=p;
		dsum[cnt]=dsum[cnt-1]+lasdis[p];
		vis[p]=1,p=f[p];
	}
	p=ed;
	memset(dis,0,sizeof(dis));
	for(i=cnt;i;i--) dsum[i]=dsum[i-1],dsum[i-1]=0;
	while(p)
	{
		for(i=head[p];i;i=e[i].next)
		{
			j=e[i].to;
			if(vis[j]) continue;
			dfs2(j,p);
			dis[p]=max(dis[j]+e[i].dis,dis[p]);
		}
		p=f[p];
	}
	//for(i=1;i<=n;i++) cout<<vis[i];
	for(i=1;i<=cnt;i++) lx[i]=max(lx[i-1]+lasdis[looker[i-1]],dis[looker[i]]);
	for(i=cnt;i>=1;i--) rx[i]=max(rx[i+1]+lasdis[looker[i]],dis[looker[i]]);
	int l=1,r=0;
	for(r=1;r<=cnt;r++)
	{
		while(dsum[r]-dsum[l]>m) l++;
		while(dis[looker[q[rr]]]<=dis[looker[r]]&&ll<=rr) rr--;
		while(q[ll]<l&&ll<=rr) ll++;
		q[++rr]=r;
		ans=min(ans,max(max(lx[l],rx[r]),dis[looker[q[ll]]]));
	}
	cout<<ans<<endl;
	return 0;
}

P4211 [LNOI2014]LCA

给定 mm 组询问问你∑i=lrdep(lca(i,j))\sum\limits_{i=l}^{r}dep(lca(i,j))

我们会求树上两点间距离dis(u,v)=dis(1,u)+dis(1,v)−2∗dis(1,lca)dis(u,v)=dis(1,u)+dis(1,v)-2*dis(1,lca)

求 dep(lca)dep(lca) 也是求是求 dis(1,lca)dis(1,lca)

因此我们把 1,u1,u 的路径 +1+1 ,再查 1,v1,v 路径上的值，就得到了 lca(u,v)lca(u,v) 的深度

这样做是 O(nmlog⁡2n)O(nm\log^2 n) 考虑其可差分性，我们可以把这个序列扫一遍

时间复杂度O(nlog⁡2n)O(n\log^2n)

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long 

using namespace std;

const int maxn=50050;
int dep[maxn],top[maxn],f[maxn],sz[maxn],id[maxn];
int preans[maxn],rans[maxn];
int target[maxn],size;
int head[maxn];
int son[maxn],cnt;
int n,m;

vector <int> st[maxn],ed[maxn];

struct edge{
	int next,to;
}e[maxn*2];

inline void addedge(int next,int to)
{
	e[++size].to=to;
	e[size].next=head[next];
	head[next]=size;
}

namespace segment_tree{
	
	#define ls i<<1
	#define rs i<<1|1
	#define lson i<<1,l,mid
	#define rson i<<1|1,mid+1,r
	
	struct tree{
		int l,r,add,sum;
	}t[maxn<<4];
	
	inline void pushup(int i)
	{
		t[i].sum=t[ls].sum+t[rs].sum; 
	}
	
	inline void pushdown(int i)
	{
		if(!t[i].add) return ;
		t[ls].add+=t[i].add;
		t[rs].add+=t[i].add;
		t[ls].sum+=(t[ls].r-t[ls].l+1)*t[i].add;
		t[rs].sum+=(t[rs].r-t[rs].l+1)*t[i].add;
		t[i].add=0;
	}
	
	void build_tree(int i,int l,int r)
	{
		t[i].l=l;
		t[i].r=r;
		if(l==r) return ;
		int mid=(l+r)>>1;
		build_tree(lson);
		build_tree(rson);
		return ;
	}
	
	void change_tree(int i,int l,int r,int x,int y,int target)
	{
		if(l>=x&&r<=y)
		{
			t[i].add+=target;
			t[i].sum+=(r-l+1)*target;
			return ; 
		}
		pushdown(i);
		int mid=(l+r)>>1;
		if(x<=mid) change_tree(lson,x,y,target);
		if(y>mid) change_tree(rson,x,y,target);
		pushup(i);
	}
	
	int ask_sum_tree(int i,int l,int r,int x,int y)
	{
		int ans=0;
		if(l>=x&&r<=y) return t[i].sum;
		pushdown(i);
		int mid=(l+r)>>1;
		if(x<=mid) ans+=ask_sum_tree(lson,x,y);
		if(y>mid) ans+=ask_sum_tree(rson,x,y);
		return ans;
	}
	
}

void dfs1(int t,int fat)
{
	int i,j;
	f[t]=fat;
	sz[t]=1;
	dep[t]=dep[fat]+1;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==fat) continue;
		dfs1(j,t);
		if(sz[son[t]]<sz[j]) son[t]=j;
	}
}

void dfs2(int t,int topt)
{
	int i,j;
	id[t]=++cnt;
	top[t]=topt;
	if(!son[t]) return ;
	dfs2(son[t],topt);
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==f[t]||j==son[t]) continue;
		dfs2(j,j);
	}
	
}

void add_tree(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		segment_tree::change_tree(1,1,n,id[top[x]],id[x],1); 
		x=f[top[x]];
	}
	if(id[x]>id[y]) swap(x,y);
	segment_tree::change_tree(1,1,n,id[x],id[y],1); 
}

int ask_tree(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans+=segment_tree::ask_sum_tree(1,1,n,id[top[x]],id[x]);
		x=f[top[x]];
	}
	if(id[x]>id[y]) swap(x,y);
	ans+=segment_tree::ask_sum_tree(1,1,n,id[x],id[y]);
	return ans;
}

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	int t1,t2,t3;
	for(i=2;i<=n;i++) cin>>t1,t1++,addedge(t1,i),addedge(i,t1);
	dfs1(1,1);
	dfs2(1,1);
	segment_tree::build_tree(1,1,n);
	for(i=1;i<=m;i++)
	{
		cin>>t1>>t2>>t3;
		t1++,t2++,t3++;
		st[t1-1].push_back(i);
		ed[t2].push_back(i);
		target[i]=t3;
	}
	for(i=1;i<=n;i++)
	{
		add_tree(1,i);
		while(!st[i].empty())
		{
			int t=st[i].size(); t--;
			preans[st[i][t]]=ask_tree(1,target[st[i][t]]);
			st[i].pop_back();
		}
		while(!ed[i].empty())
		{
			int t=ed[i].size(); t--;
			rans[ed[i][t]]=ask_tree(1,target[ed[i][t]]);
			ed[i].pop_back();
		}
	}
	for(i=1;i<=m;i++) cout<<(rans[i]-preans[i])%201314<<endl;
	return 0;
}

CF1000G Two-Paths

每条边可以走最多两次，边权为 valto−k∗wval_{to}-k*w 询问从一个点到另一个点的最大值

我们分析其中一次询问

对于 xx 到 yy 的路径，我们必须经过，这个东西我们用前缀和记录这里的点权和边权

同时，我们可以走这个路径上任意一点的子树，对于 lcalca 我们还可以访问祖先，以及除了lca的兄弟

因此我们设 f(x),g(x),h(x)f(x),g(x),h(x) 分别表示子树（不包括自己）收益最大值，兄弟收益最大值，祖先（不包括自己）收益最大值

转移方程很容易想出来

f(x)=∑j∈son(x)max⁡(0,f[j]+val[j]−2∗w)f(x)=\sum\limits_{j\in \text{son}(x)}\max(0,f[j]+val[j]-2*w)

g(x)={f(x)if  f[j]+val[j]−2∗w≤0f(x)−profitelseg(x)=\begin{cases}f(x)& if~ ~f[j]+val[j]-2*w\leq0\\f(x)-profit& else\end{cases}

h(x)=g(x)+h(father)−wh(x)=g(x)+h(father)-w

询问答案的时候，注意两个细节

1.是否一个点是另一个点的祖先

2.是否统计了两次 g(lca)g(lca)

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=3e5+20;

int f[maxn],h[maxn],g[maxn],gsum[maxn];
int n,m,head[maxn];
int val[maxn],contribution[maxn];
int gmmx[maxn],gmx[maxn];
int valsum[maxn]; 
int dis[maxn];
int dep[maxn];
int fat[25][maxn],size;

struct edge{
	int next,to,dis;
}e[maxn<<1];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

void dfs1(int t,int ffat)
{
	int profit=0;
	int i,j,k;
	fat[0][t]=ffat;
	dep[t]=dep[ffat]+1;
	valsum[t]+=val[t];
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		k=e[i].dis;
		if(j==ffat) continue;
		dis[j]=dis[t]+k;
		valsum[j]=valsum[t];
		dfs1(j,t);
		if(f[j]-2*k+val[j]>0)
		{
			contribution[j]=1;
			profit=f[j]-2*k+val[j];
			f[t]+=profit;
		}
	}
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		k=e[i].dis;
		if(j==ffat) continue;
		if(contribution[j])
		{
			profit=f[j]+val[j]-2*k;
			g[j]=f[t]-profit;
		}
		else g[j]=f[t];
		if(g[j]>=g[gmmx[t]]) gmx[t]=gmmx[t],gmmx[t]=j;
		else if(g[j]>=g[gmx[t]]) gmx[t]=j;
	}
}

void dfs2(int t,int ffat)
{
	int i,j,k;
	gsum[t]+=g[t];
	for(int i=1;i<=20;i++)
	{
		fat[i][t]=fat[i-1][fat[i-1][t]];
		//s[i][t]=s[i-1][t]+s[i-1][fat[i-1][t]]-f[fat[i-1][t]];
	}
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		k=e[i].dis;
		if(j==ffat) continue;
		gsum[j]+=gsum[t];
//		if(contribution[j]) 
//		{
//			int profit=f[j]+val[j]-2*k;
//			//s[j][0]-=profit;
//		}
		if(j==gmmx[t]) h[j]=max(-k*2+val[t]+h[t]+g[j],h[j]);
		else h[j]=max(-k*2+val[t]+h[t]+g[j],h[j]);
//		if(j==gmmx[t]) h[j]=max(-k*2+val[t]+g[gmx[t]],h[j]);
//		else h[j]=max(-k*2+val[t]+g[gmmx[t]],h[j]);
		dfs2(j,t);
	}
}

int getlca(int x,int y)
{
	if(x==y) return x;
	if(dep[x]<dep[y]) swap(x,y);
	int delta=dep[x]-dep[y];
	if(dep[x]>dep[y]) 
	for(int i=20;i>=0;i--) if(delta>=(1<<i)) delta-=(1<<i),x=fat[i][x];
	for(int i=20;i>=0;i--)
	{
		if(fat[i][x]!=fat[i][y]) 
		{
			x=fat[i][x];
			y=fat[i][y];
		}
	}
	if(x==y) return x;
	return fat[0][x];
}

int fakelca(int x,int y)
{
	if(x==y) return 0;
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[fat[i][x]]>dep[y]) 
		{
			x=fat[i][x];
		}
	}
	return x;
}

int getans(int x,int y)
{
	int mustans=0;
	if(dep[x]>dep[y]) swap(x,y);
	int lca=getlca(x,y);
	//mustans=dep[x]+dep[y]-dep[lca]-dep[llca];
	//	mustans=;
	if(lca==1) mustans-=dis[x]+dis[y]-dis[lca],mustans+=valsum[y]+valsum[x]-valsum[lca];
	else mustans-=dis[x]+dis[y]-2*dis[lca],mustans+=valsum[y]+valsum[x]-valsum[lca]-valsum[fat[0][lca]]; 
	if(x==lca)
	{
		return gsum[y]-gsum[x]+h[x]+f[y]+mustans; 
	}
	int l1,l2;
	l1=fakelca(x,lca);
	l2=fakelca(y,lca);
	mustans+=f[x]+f[y]+h[lca];
	mustans+=gsum[x]-gsum[l1]+gsum[y]-gsum[l2];
	mustans+=g[l1];
	if(contribution[l2])
	{
		mustans-=f[l2]+val[l2]-2*(dis[l2]-dis[lca]);
	}
	return mustans;
	//if(contribution[x]) mustans-=(val[x]-2*(dis[fat[x][0]]-dis[x]));
	//return mustans+f[fat[0][x]]+h[fat[x][0]];
}

inline void qread(int &ans)
{
	ans=0;
	int f=1;
	static char c=getchar();
	while(!isdigit(c)) {if(c=='-') f=-1; c=getchar();}
	while(isdigit(c)) ans=ans*10+c-'0',c=getchar();
	ans=ans*f;
}

signed main()
{
	//ios::sync_with_stdio(false);
	register int i,j;
	qread(n);qread(m); 
	int t1,t2,t3;
	for(i=1;i<=n;i++) qread(val[i]);
	for(i=1;i<n;i++)
	{
		qread(t1); qread(t2); qread(t3);
		addedge(t1,t2,t3);
		addedge(t2,t1,t3);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(i=1;i<=m;i++)
	{
		qread(t1);
		qread(t2);
		printf("%lld\n",getans(t1,t2));
	}
	return 0;
}

CF1009F Dominant Indices

一个长链剖分的模板题。

为什么会想到长链剖分：1.子树状态可以继承2.与深度有关？

其实是在学长链剖分

直接继承长儿子的状态（可以用指针 O(1)O(1) 求），然后暴力合并其他的，这个复杂度显然是 O(N)O(N)

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=1e6+6;

int n,head[maxn],*f[maxn];
int ans[maxn],tmp[maxn],*st=tmp,size,dis[maxn],son[maxn],sz[maxn];

struct edge{
	int next,to,dis;
}e[maxn<<1];

inline void addedge(int next,int to,int dis=0)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

inline void dfs1(int t,int fat=0)
{
	int i,j;
	//int sz[t]=1;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==fat) continue;
		dfs1(j,t);
		//sz[t]+=sz[j];
		if(dis[j]>dis[son[t]]) son[t]=j;
	}
	dis[t]=dis[son[t]]+1;
}

inline void dfs2(int t,int fat=0)
{
	int i,j;
	f[t][0]=1;
	if(!son[t]) 
	{
		ans[t]=0;
		return ;
	}
	f[son[t]]=f[t]+1;
	dfs2(son[t],t);
	int k;
	ans[t]=ans[son[t]]+1;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==fat||j==son[t]) continue;
		f[j]=st; st+=dis[j]; dfs2(j,t);
		for(k=1;k<=dis[j];k++)
		{
			f[t][k]+=f[j][k-1];
			if(f[t][k]>f[t][ans[t]])  ans[t]=k;
			else if(f[t][k]==f[t][ans[t]]) ans[t]=min(ans[t],k);
		}
	}
	if(f[t][ans[t]]==1) ans[t]=0;
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n;
	int t1,t2;
	for(i=1;i<n;i++) cin>>t1>>t2,addedge(t1,t2),addedge(t2,t1);
	dfs1(1,1);
	f[1]=st,st+=dis[1];
	dfs2(1,1); 
	for(i=1;i<=n;i++) cout<<ans[i]<<endl; 
	return 0;
}

P5384 【[Cnoi2019]雪松果树】

显然的一个长链剖分，询问某些点 kk级儿子个数，因此对每一个询问都在目标点牵链（由于重子树会合并所以不能在线做），然后倍增处理，貌似就做完了。

然后你就被卡成了 MLE 40分

本来之前深度设为15还能过，不过hack数据貌似把这个卡了，依然过不了，然后一怒之下，倍增从每次倍增2变成每次倍增4，空间减小一半但是时间变成原来的三倍（每次最多向上跳一次变成了每次最多向上跳三次），时间复杂度还是 O(nlog⁡n)O(n\log n) (虽然常数大了点，但是卡卡还是能过的)

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
128
129
130
131
132
133
#include<touwenjian.h>

using namespace std;

const int maxn=1e6+10;

int head[maxn],dis[maxn],size,son[maxn],*f[maxn],tmp[maxn],*fst=tmp;
int _fat[maxn][11],n,m,hd[maxn];
int dep[maxn],sz,ans[maxn];
int que[maxn];

struct edge{
	int next,to,dis;
}e[maxn],ask[maxn];

inline void addask(int next,int to)
{
	ask[++sz].to=to;
	ask[sz].next=hd[next];
	hd[next]=sz;
}

inline void addedge(int next=0,int to=0,int dis=0)
{
	e[++size].to=to;
	e[size].next=head[next];
	head[next]=size;
}

inline void qread(int &x)
{
	x=0; int f=1;
	static char c=getchar();
	while(!isdigit(c)) {if(c=='-') f=-1; c=getchar();}
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	x=x*f; return ;
}

inline void qread(int &x,int &y)
{
	qread(x),qread(y);
}

void dfs1(int t,int fat=0)
{
	int i,j;
	dep[t]=dep[fat]+1;
	for(i=1;(1<<(i*2))<=dep[t];i++) 
	_fat[t][i]=_fat[_fat[t][i-1]][i-1]; 
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==fat) continue;
		dfs1(j,t);
		if(dis[j]>dis[son[t]]) son[t]=j;
	}
	dis[t]=dis[son[t]]+1;
}

void dfs2(int t,int fat=0)
{
	f[t][0]=1;
	int i,j,k;
	if(!son[t]) 
	{
		for(i=hd[t];i;i=ask[i].next)
		{
			j=ask[i].to;
			ans[j]=f[t][que[j]]-1;
		}
		return ;
	}
	f[son[t]]=f[t]+1;
	dfs2(son[t],t); 
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==son[t]||j==fat) continue;
		f[j]=fst; fst+=dis[j];
		dfs2(j,t);
//		printf("%d ",j);
		for(k=1;k<=dis[j];k++) f[t][k]+=f[j][k-1];
//		printf("%d ",f[j][k]);
//		printf("\n");
	}
	for(i=hd[t];i;i=ask[i].next)
	{
		j=ask[i].to;
		ans[j]=f[t][que[j]]-1;
	}
}

int targetpoint(int x,int k)
{
	//if(k==0) return x;
	if(dep[x]<k) return 0;
	for(int i=10;i>=0;i--)
	{
		for(int j=1;j<=3;j++)
		{
			if(k<(1<<(i*2))) continue;
			x=_fat[x][i]; 
			k-=(1<<i);
		}
	}
	while(k--) x=_fat[x][0];
	return max(0,_fat[x][0]);
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	qread(n,m);
	int t1,t2,t3;
	for(i=2;i<=n;i++) qread(t1),addedge(t1,i),_fat[i][0]=t1;
	_fat[1][0]=0;
	dfs1(1,1);
	f[1]=fst;fst+=dis[1];
	for(i=1;i<=m;i++)
	{
		qread(t1,t2);
		t3=t1;
		t1=targetpoint(t1,t2-1);
		t2=dep[t3]-dep[t1];
		que[i]=t2;
		addask(t1,i);
	}
	dfs2(1,1);
	for(i=1;i<=m;i++) printf("%d ",ans[i]);
	return 0;
}

P4168 [Violet]蒲公英

呜呼终于会了

O(nn)O(n\sqrt{n}) 空间

记录两个数组f[i][j],g[i][j]f[i][j],g[i][j] 表示 ii 到 jj 区间的众数和 ii 区间（包含ii ）以前的 jj 的个数

按照分块把答案分成三个区间，中间的区间直接统计答案，两边的区间暴力统计，块长为n\sqrt{n} 最优

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=40400;
const int maxl=210;

int f[maxl][maxl],g[maxl][maxn];
int n,len,bl[maxn],a[maxn];
int b[maxn],tot;
int tmp[maxn];
int m;

inline void _prework()
{
	int i,j,k;
	for(i=1;i<=bl[n];i++)
	{
		memset(tmp,0,sizeof(tmp));
		int st;
		int mmx=0;
		for(j=i;j<=bl[n];j++)
		{
			st=(j-1)*len+1;
			int r=min(j*len,n);
			for(k=st;k<=r;k++)
			{
				tmp[a[k]]++;
				if((tmp[a[k]]==tmp[a[mmx]]&&a[k]<=a[mmx])||tmp[a[k]]>tmp[a[mmx]]) mmx=k;
			}
			f[i][j]=mmx;
		}
	}
	for(i=1;i<=n;i++) 
	{
		g[bl[i]][a[i]]++;
	}
	for(i=1;i<=bl[n];i++)
	for(j=1;j<=n;j++)
		g[i][j]+=g[i-1][j];
	memset(tmp,0,sizeof(tmp));
}

inline int getans(int l,int r)
{
	int i,j,mmx=0,ans;
	if(bl[l]==bl[r]||bl[l]+1==bl[r])
	{
		for(i=l;i<=r;i++)
		{
			tmp[a[i]]++;
			if((tmp[a[i]]==tmp[a[mmx]]&&a[i]<a[mmx])||tmp[a[i]]>tmp[a[mmx]]) mmx=i;
		}
		ans=b[a[mmx]];
		for(i=l;i<=r;i++)
		{
			tmp[a[i]]--;
		}
		return ans;
	}
	mmx=f[bl[l]+1][bl[r]-1];
	int lok=a[mmx];
	tmp[a[mmx]]+=g[bl[r]-1][a[mmx]]-g[bl[l]][a[mmx]];
	for(i=l;i<=bl[l]*len;i++)
	{		
		if(!tmp[a[i]]) tmp[a[i]]+=g[bl[r]-1][a[i]]-g[bl[l]][a[i]];
		tmp[a[i]]++;
		if(tmp[a[i]]>tmp[a[mmx]]||(tmp[a[i]]==tmp[a[mmx]]&&a[i]<a[mmx])) mmx=i;
	}
	for(i=(bl[r]-1)*len+1;i<=r;i++)
	{
		if(!tmp[a[i]]) tmp[a[i]]+=g[bl[r]-1][a[i]]-g[bl[l]][a[i]];
		tmp[a[i]]++;
		if(tmp[a[i]]>tmp[a[mmx]]||(tmp[a[i]]==tmp[a[mmx]]&&a[i]<a[mmx])) mmx=i;		
	}
	tmp[lok]=0;
	for(i=l;i<=bl[l]*len;i++) tmp[a[i]]=0;//cout<<a[i]<<" ";
	for(i=(bl[r]-1)*len+1;i<=r;i++) tmp[a[i]]=0;//cout<<a[i]<<" ";
	//cout<<endl;
	return b[a[mmx]];
}

signed main()
{
	//freopen("1.in","r",stdin);
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
	len=sqrt(n);
	sort(b+1,b+n+1); tot=unique(b+1,b+n+1)-b-1;
	for(i=1;i<=n;i++) a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
	for(i=1;i<=n;i++) bl[i]=(i-1)/len+1;
	_prework();
	int l,r,lasans=0;
	for(i=1;i<=m;i++)
	{
		cin>>l>>r;
		l=(l+lasans-1)%n+1;
		r=(r+lasans-1)%n+1;
		if(l>r) swap(l,r);
		lasans=getans(l,r);
		cout<<lasans<<endl;
	}
	return 0;
}