qyc 讲题汇总。先讲我听懂的。

动态图连通性

题意简述

维护一张点数为 $n$ 的无向简单图，$m$ 次操作，加入或删除一条边及查询两个点是否连通。

$n\leq 5\times 10^3,m\leq 5\times 10^5$。

解法一：线段树分治（离线）

在时间轴上，每条边都有自己存在的时间段。我们在操作的时间轴上建立一棵线段树，每条边插入进其所完全包含的线段树上 $O(\log m)$ 个区间上。

在线段树上进行 DFS，同时维护一个表示连通块的并查集。这个并查集被要求是支持撤销操作的，为此我们使用按秩合并，每次修改时记录 fa 变化的那个点。每当我们进入一个线段树节点时，把节点里的所有边加入到并查集中，离开时撤销掉。当递归到叶子节点时计算询问。

容易证明这是正确的，因为当我们递归到叶子节点的时候，所有包含这一时间点的边都已经被加入到并查集中，同时撤销操作保证了没有包含这一节点的边不在并查集中。

分析一下时间复杂度。单个询问处理 $O(\log n)$，并查集合并 $O(\log n)$，撤销 $O(1)$。因为在线段树上，原来的 $O(m)$ 条边被拆分成了 $O(m\log m)$ 条边，每条边分别被合并撤销一次，所以是 $O(m\log n\log m)$ 的。

代码注意按秩合并别写假了，还有就是合并一条边时其可能已经被合并了，不能单单按照数量来进行撤销。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp(x,y) make_pair(min(x,y),max(x,y))
#define pb push_back
const int N=5e3+10,M=5e5+10;
int n,m;
int fa[N],siz[N],st[M],top;
int find(int x){while(fa[x]) x=fa[x]; return x;}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(siz[x]>siz[y])swap(x,y);
    st[++top]=x;
    if(x==y)return;
    fa[x]=y,siz[y]+=siz[x];
}
void quash(){
    if(fa[st[top]]!=st[top])siz[fa[st[top]]]-=siz[st[top]],fa[st[top]]=0;
    top--;
}
bool conn(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return 1;
    else return 0;
}
vector<pii> t[M*4];
pii qr[M];
bool ans[M];
void update(int p,int l,int r,int L,int R,pii e){
    if(L<=l&&r<=R){
        t[p].pb(e);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m)update(p*2,l,m,L,R,e);
    if(R>m)update(p*2+1,m+1,r,L,R,e);
}
void dfs(int p,int l,int r){
    int m=(l+r)>>1;
    for(pii pa:t[p])merge(pa.fi,pa.se);
    if(l==r){
        if(qr[l].fi)cout<<(conn(qr[l].fi,qr[l].se)?'Y':'N')<<'\n';
    }else dfs(p*2,l,m),dfs(p*2+1,m+1,r);
    for(int i=0;i<t[p].size();i++)quash();
}
map<pii,vector<int> >ap;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) siz[i]=1;
    for(int i=1;i<=m;i++){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==2)qr[i]=mp(x,y);
        else ap[mp(x,y)].push_back(i);
    }
    for(pair<pii,vector<int> > p:ap){
        int lst=0;
        for(int x:p.se){
            if(!lst)lst=x;
            else update(1,1,m,lst,x-1,p.fi),lst=0;
        }
        if(lst)update(1,1,m,lst,m,p.fi);
    }
    dfs(1,1,m);
    return 0;
}

解法二：LCT（在线）

不会。

CF1442D Sum

题意简述

给定 $n$ 个不降的数组 $a_i$，你需要执行 $k$ 次操作：选择其中一个数组的首个元素并将其拿出来。最大化拿出来元素的和。

$\sum |a_i|\leq 10^6,n,k\leq 3\times 10^3$。

解法：线段树分治

注意到一个关键结论：如果你选了某个数组的元素，那么你要么把这个数组选完，要么因为剩余次数不够而选一个前缀。

所以可以把 $n$ 个数组看成 $n$ 个物品，费用是 $|a_i|$，价值是 $\sum a_i$。每次枚举没选完的那个数组，对剩下的数组做 $0/1$ 背包。但这样是 $O(nk^2)$ 的，显然过不了。

考虑到每次 $0/1$ 背包时，数据有很大一部分是重复的，所以我们考虑使用线段树分治来使数据利用最大化。

具体地，在 $1$ 到 $n$ 上建立线段树。进入一个节点时，从其父亲那继承背包的 DP 数组，把 $m+1$ 到 $r$ 的数组加入背包，向左递归，然后清空，把 $l$ 到 $m$ 的数组加入背包，向右递归。到达叶子节点时，除了这个节点的数组，其他的都已加入背包，所以直接枚举这个数组选了几个，跟背包的 DP 数组结合统计答案。正确性显然。

分析一下复杂度。把一个数组加入背包是 $O(k)$ 的。递归每一层都要加入 $n$ 个数组，一共有 $\log n$ 层，单个叶子节点统计答案复杂度是 $O(k)$ 的。所以总复杂度是 $O(nk\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
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
#define pb push_back 
const int N=3e3+10;
int n,k,t[N];
vector<int> s[N];
int w[N],v[N];
int ans=0,sum;
void solve(int l,int r,int *a){
    if(l==r){
        for(int i=0;i<=min(k,t[l]);i++)
            ans=max(ans,a[k-i]+s[l][i]);
        return;
    }
    int m=(l+r)>>1;
    int *f=new int[sum+100];
    memcpy(f,a,sizeof(int)*(sum+10));
    for(int i=l;i<=m;i++)
        for(int j=sum;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    solve(m+1,r,f);
    memcpy(f,a,sizeof(int)*(sum+10));
    for(int i=m+1;i<=r;i++)
        for(int j=sum;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    solve(l,m,f);
    delete[] f;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>t[i];
        s[i].pb(0);
        for(int j=1;j<=t[i];j++){
            int x;cin>>x;
            s[i].pb(s[i][j-1]+x);
        }
        v[i]=s[i][t[i]];
        w[i]=t[i];
    }
    sum=k;
    int *f=new int[sum+100];
    memset(f,0,sizeof(int)*(sum+10));
    solve(1,n,f);
    cout<<ans<<'\n';
    return 0;
}