CF600E
线段树合并典题。
P3899
可以发现 \(a\) 固定了所以可以分讨。
- 当 \(a\) 在 \(b\) 下面时，可以发现 \(b\) 能取的个数是 \(\min(k,dep_a-1)\) 而 \(c\) 的个数就是 \(siz_a-1\) 然后乘起来就是总方案数。
- 当 \(a\) 在 \(b\) 上面时，可以推出 \(dep_b-dep_a\leq k\) 并且 \(b\) 在 \(a\) 的子树中，而 \(c\) 的方案数就是 \(siz_b-1\) 那么只需要用主席树维护区间在 \(dfn_x\sim lst_x\) 之间的点且 \(dep_x\leq dep_a+k\) 的 \(siz_x-1\) 之和即可。
P7215
考虑连边，我们用 \(i\to j\) 表示如果 \(i\) 要合法那么一定要合并 \(j\) 城镇所以我们可以发现最后合法的一定是一个无出边的连通块，那么我们考虑如何连边首先我们发现可以将一种颜色的点按照 dfs 序排序然后两两之间的路径一定包含了所有能经过的，所以我们可以对于每对路径之间的点都会被此颜色连边而转移到 dfs 序上就是此颜色回向一段连续的区间连边，那么考虑线段树优化建图由于只有转到树剖上才能使 dfs 序连续所以考虑用树剖优化来建图，最后跑一边 tarjan 统计连通块中颜色小于等于 \(k\) 的点数最小且无出边的连通块即可。
P3703
考虑用线段树维护根节点到 \(x\) 的答案，然后我们考虑对于每次修改一定是将 \(1\sim x\) 的路径上的答案，对于修改 \(1\) 可以考虑树剖去修改 \(1\sim x\) 上的值，对于能影响到的点只需要记录一个颜色最上面的点和最下面的点然后每次暴力往上跳并用线段树修改即可，并且将 \(1\sim x\) 上的颜色全部染成 \(x\)，对于修改 \(2\) 我们可以发现答案等于 \(dep_x+dep_y-2\times dep_{lca_{x,y}}+1\)，对于修改 \(3\) 的答案就是 \(dfn_x\sim dfs_x+siz_x-1\) 这一段中答案的最大值。
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
if(x<0) printf("-"),x=-x;
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
x = 0; char ch = getchar();
int f = 1;
while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
x *= f;
}
int T=1;
const int N=1e5+10;
int dfn[N],siz[N],son[N],dep[N];
int top[N],mp[N],f[N][20],n;
vector<int>v[N];
struct node{
int l,r;
int Max;
int tag1;
}tr[N<<2];
struct Node{
int l,r;
int val,tag;
}tt[N<<2];
void build1(int u,int l,int r) {
tt[u]={l,r};
if(l==r) {
tt[u].val=mp[l];
return;
}
int mid=l+r>>1;
build1(u<<1,l,mid);
build1(u<<1|1,mid+1,r);
}
void down1(int u) {
if(tt[u].tag) {
tt[u<<1].tag=tt[u].tag;
tt[u<<1|1].tag=tt[u].tag;
tt[u<<1].val=tt[u].tag;
tt[u<<1|1].val=tt[u].tag;
tt[u].tag=0;
}
}
void add(int u,int l,int r,int val) {
if(tt[u].l>=l&&tt[u].r<=r) {
tt[u].tag=tt[u].val=val;
return;
}
down1(u);
int mid=tt[u].l+tt[u].r>>1;
if(mid>=l) add(u<<1,l,r,val);
if(mid<r) add(u<<1|1,l,r,val);
}
int get_yan(int u,int x) {
if(tt[u].l==tt[u].r) return tt[u].val;
down1(u);
int mid=tt[u].l+tt[u].r>>1;
if(mid>=x) return get_yan(u<<1,x);
return get_yan(u<<1|1,x);
}
void up(int x) {
tr[x].Max=max(tr[x<<1].Max,tr[x<<1|1].Max);
}
void down(int x) {
if(tr[x].tag1) {
tr[x<<1].tag1+=tr[x].tag1;
tr[x<<1|1].tag1+=tr[x].tag1;
tr[x<<1].Max+=tr[x].tag1;
tr[x<<1|1].Max+=tr[x].tag1;
tr[x].tag1=0;
}
}
void build(int u,int l,int r) {
tr[u]={l,r};
if(l==r) {
tr[u].Max=dep[mp[l]];
return;
}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
up(u);
}
void dfs(int x,int fa) {
siz[x]=1;
f[x][0]=fa;
dep[x]=dep[fa]+1;
for(auto to:v[x]) {
if(to==fa) continue;
dfs(to,x);
siz[x]+=siz[to];
if(siz[son[x]]<siz[to]) son[x]=to;
}
}
int L[N],R[N];
void init() {
rep(j,1,19) rep(i,1,n) f[i][j]=f[f[i][j-1]][j-1];
}
int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
rep1(i,19,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
rep1(i,19,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int idx;
void modify1(int u,int l,int r,int k) {
if(tr[u].l>=l&&tr[u].r<=r) {
tr[u].tag1+=k;
tr[u].Max+=k;
return;
}
down(u);
int mid=tr[u].l+tr[u].r>>1;
if(mid>=l) modify1(u<<1,l,r,k);
if(mid<r) modify1(u<<1|1,l,r,k);
up(u);
}
void dfs1(int x,int head) {
top[x]=head;
dfn[x]=++idx;
mp[idx]=x;
if(!son[x]) return;
dfs1(son[x],head);
for(auto to:v[x]) if(!dfn[to]) dfs1(to,to);
}
int Ans(int u,int l,int r) {
if(tr[u].l>=l&&tr[u].r<=r) {
return tr[u].Max;
}
int mid=tr[u].l+tr[u].r>>1,res=0;
down(u);
if(mid>=l) res=Ans(u<<1,l,r);
if(mid<r) res=max(res,Ans(u<<1|1,l,r));
return res;
}
void gai(int x,int y,int k){
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
add(1,dfn[top[x]],dfn[x],k);
x=f[top[x]][0];
}
if(dfn[x]>dfn[y]) swap(x,y);
add(1,dfn[x],dfn[y],k);
}
int m;
int jump(int x,int t) {
rep1(i,19,0) if(dep[f[x][i]]>dep[t]) x=f[x][i];
return x;
}
void change(int x) {
while(x) {
int xx=get_yan(1,dfn[x]);
int rr=R[xx];
modify1(1,dfn[L[xx]],dfn[L[xx]]+siz[L[xx]]-1,-1);
int ff=0;
if(xx!=x) {
int now=jump(xx,x);
ff=now;
modify1(1,dfn[now],dfn[now]+siz[now]-1,1);
}
x=f[L[xx]][0];
if(ff!=0) L[xx]=ff;
}
}
void solve() {
in(n),in(m);
rep(i,1,n-1) {
int x,y;
in(x),in(y);
v[x].pb(y);
v[y].pb(x);
}
rep(i,1,n) L[i]=R[i]=i;
dfs(1,0);
dfs1(1,1);
build(1,1,n);
build1(1,1,n);
init();
while(m--) {
int opt;
in(opt);
if(opt==1) {
int x;
in(x);
modify1(1,1,n,1);
int xx=get_yan(1,dfn[x]);
int ll=L[xx];
modify1(1,dfn[ll],dfn[ll]+siz[ll]-1,-1);
if(x!=xx) {
int now=jump(xx,x);
modify1(1,dfn[now],dfn[now]+siz[now]-1,1);
}
change(f[L[xx]][0]);
gai(1,x,x);
if(xx!=x) L[xx]=jump(xx,x);
else L[xx]=0;
L[x]=1,R[x]=x;
}else if(opt==2){
int x,y;
in(x),in(y);
int fa=lca(x,y);
printf("%lld\n",Ans(1,dfn[x],dfn[x])+Ans(1,dfn[y],dfn[y])-2*Ans(1,dfn[fa],dfn[fa])+1);
}else {
int x;
in(x);
printf("%lld\n",Ans(1,dfn[x],dfn[x]+siz[x]-1));
}
}
}
fire main() {
while(T--) {
solve();
}
return false;
}
CF1418G
没脑子题，考虑分治，我们可以将左右能匹配的用哈希来让其匹配那么就成了左边一个桶然后枚举右边的判断是否能接上即可，这里我们可以对 \(j\) 第 \(i\) 次出现给他一个值然后让左边的 \(1\) 次的值能与右边地 \(2\) 次出现的值抑或为 \(0\) 但是我们发现对于左右同一个值都出现了 \(3\) 次的情况也会被计入答案那么我们对于每一个 \(i\sim mid\) 的后缀算出一个右端点能到的最大值 \(r\) 只需要在 \(mid+1\sim r\) 查询 \(x\) 的出现次数即可，直接主席树即可。
void get(int l,int r) {
if(r-l+1<3) return;
int mid=l+r>>1;
get(l,mid);
get(mid+1,r);
idx=false;
int s=0;
rep(i,l,r) cnt[a[i]]=0;
rt[mid]=false;
cc=0;
rep(i,l,r) {
int aa=rnd64(),bb=rnd64(),cc=rnd64();
mp[a[i]][1]=aa*cc;
mp[a[i]][2]=bb;
ma[a[i]][1]=bb;
ma[a[i]][2]=aa*cc;
}
rep(i,l,r) {
rt[i]=0;
int aa=rnd64(),bb=rnd64(),cc=rnd64();
mpp[a[i]][1]=aa*cc;
mpp[a[i]][2]=bb;
maa[a[i]][1]=bb;
maa[a[i]][2]=aa*cc;
}
vector<int>v;
int tot=0;
int s1=0,Maxx=0;
rep(i,mid+1,r) {
cnt[a[i]]++;
if(cnt[a[i]]>3) break;
Maxx=i;
s^=mp[a[i]][cnt[a[i]]];
s^=mp[a[i]][cnt[a[i]]-1];
s1^=mpp[a[i]][cnt[a[i]]];
s1^=mpp[a[i]][cnt[a[i]]-1];
val[i]={s,s1};
arr[++cc]={s,s1};
}
s1=0;
sort(arr+1,arr+1+cc);
int mm=unique(arr+1,arr+1+cc)-arr-1;
rep(i,l,r) cnt[a[i]]=0;
rep(i,mid+1,r) {
cnt[a[i]]++;
if(cnt[a[i]]>3) break;
rt[i]=rt[i-1];
int id=lower_bound(arr+1,arr+1+mm,val[i])-arr;
rt[i]=modify(rt[i],1,mm,id);
}
s=0;
rep(i,l,r) cnt[a[i]]=0,head[a[i]]=0;
s1=0;
int Max=Maxx+1;
rep1(i,mid,l) {
cnt[a[i]]++;
if(!head[a[i]]) head[a[i]]=i;
if(cnt[a[i]]>3) break;
Max=min(Max,nxt[head[a[i]]][4-cnt[a[i]]]);
s^=ma[a[i]][cnt[a[i]]];
s^=ma[a[i]][cnt[a[i]]-1];
s1^=maa[a[i]][cnt[a[i]]];
s1^=maa[a[i]][cnt[a[i]]-1];
int id=lower_bound(arr+1,arr+1+mm,make_pair(s,s1))-arr;
if(arr[id]!=make_pair(s,s1)) continue;
res+=Ans(rt[Max-1],1,mm,id);
}
}
下面是抄的，写的比较好。
n = read();
for (re int i = 1;i <= n;i++) tmp[i] = {rnd(),rnd()};
for (re int i = 1;i <= n;i++){
vis[arr[i] = read()]++;
if (vis[arr[i]] % 3 == 1) val[i] = tmp[arr[i]].fst;
else if (vis[arr[i]] % 3 == 2) val[i] = tmp[arr[i]].snd;
else val[i] = tmp[arr[i]].fst ^ tmp[arr[i]].snd;
}
for (re int i = 1;i <= n;i++) val[i] ^= val[i - 1];
fill(vis + 1,vis + n + 1,0); num[0]++;
for (re int i = 1,j = 1;j <= n;j++){
vis[arr[j]]++;
while (vis[arr[j]] > 3){
vis[arr[i]]--; num[val[i - 1]]--;
i++;
}
ans += num[val[j]]++;
} printf("%lld",ans);
CF489F
我们可以统计给定的 \(m\) 行中每一列有多少个 \(1\) 然后我们考虑对于每一列去 dp 我们定义 \(f_{i,j,k}\) 表示现在处理了前 \(i\) 列有 \(j\) 行上是 \(0\) 个 \(1\)，有 \(k\) 行上有 \(1\) 个 \(1\) 然后随便转移一下即可。
CF1744F
因为 \(mex>med\) 所以 \(0\sim med\) 的值一定都是出现过的，那么我们考虑枚举中位数 \(x\) 然后求出 \(0\sim x\) 都出现的最小区间 \(l\sim r\) 然后我们发现当区间长度等于 \(2\times (x+1)\) 或 \(2\times (x+1)-1\) 才能满足条件所以考虑对于一个区间求从左右选一个后缀和前缀使其长度为 \(x\) 的答案即可，这个可以直接推柿子。
CF323C
因为这是两个排列所以可与第一个序列来建立主席树下标是它在第二个序列中出现的位置，然后主席树就做完了。
CF903D
发现如果全部都算 \(y-x\) 那么可以用一颗树状数组解决，而此答案对于正确答案就只多了 \(|y-x|=1\) 的所以考虑每次扫过去开桶记录然后每次把多加的减去即可。
CF1468A
发现对于一个数 \(x\) 它前面的两个数中至少有一个小于等于 \(x\) 所以考虑定义状态 \(f_i\) 表示到 \(i\) 能选的最多的点，转移为 \(f_i=f_j+cnt_{j,i}\) 其中 \(a_i\geq a_j,j<i\) 且 \(cnt_{i,j}\) 表示 \(i+1\sim j-1\) 中是否有数 \(\geq a_j\)，有则为 \(1\) 否则为 \(0\)。这是 \(n^2\) 的考虑优化，发现对于每个点可以求出其前面最靠近他的一个 \(\geq a_i\) 的点，当 \(j\leq lst_i\) 时将 \(f_i\) 加一否则不加，所以考虑主席树，我们只需要在 \(lst_i\) 的主席树上找 \(a_j\leq a_i\) 的最大的 \(f_j+1\) 即可，后面的一坨就是第 \(i-1\) 棵树上的最大值。
标签：cnt,记录,int,arr,mid,xx,dfn From： https://www.cnblogs.com/highkj/p/18656716