F

双指针 扫描线 线段树

确定两个指针把数组分成三段，求一个方案使得三个集合的交集最大

有两个指针的位置需要确定，显然考虑枚举，然后对每个确定三个集合交集最大的的位置

对于每种元素，想要这个元素出现在交集里，也就是三个集合都有这个元素，如果确定，设这个元素在里最左出现位置是，最右出现是，那么想让三个区间里都有这个元素，可以位于这区间。

也就是对于每个元素都有个可以位于的区间，然后对于一个位置，的话，交集的大小，就是覆盖这个的区间个数。

那么这就是一个区间加，球单点最值，线段树维护即可。

具体就是，用一个数组维护左侧这个集合的元素，枚举，扫描整个原序列，如果的位置是一个左侧集合未出现的元素，我们就新增了一个区间，这个区间就是前面说的，进行区间加。

如果扫过的这个元素在左侧集合已经出现过了，就不是新增一个区间，而是这个元素对应的区间的范围需要变化，具体来说是需要缩小，因为原本这个位置，是这个元素在这个集合里的出现，现在移动，把这个元素挪到里了那我们必须至少让这个集合里也有一个这个元素，所以的位置，会变成当前的，也就是这一段会无效，对这段进行区间减。

对每个的位置，更新完线段树后，都进行全局最大值和最大值位置的查询，查出来的就是当前的最大交集大小，和最优位置，用他们更新答案

这里需要一个可以返回最大值和最大值位置的线段树。并且更新时可能，活不存在，也就是后面只有两个和一个这种元素的情况，需要特判

比较坑人的点是的话，也要随便选一组输出，也就是的初始值也要是一组有意义的值。

#include <bits/stdc++.h>
#define int long long


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;

struct tree{
    #define ls u<<1
    #define rs u<<1|1
    struct  node
    {
        int l,r;
        int mx,add,mxpos;

        node operator+(const node &o){
            node res;
            res.l=l;
            res.r=o.r;
            if(mx>o.mx){
                res.mx=mx;
                res.mxpos=mxpos;
            }
            else{
                res.mx=o.mx;
                res.mxpos=o.mxpos;
            }
            return res;
        }
    }tr[N<<2];
    
    void pushup(int u){
        if(tr[ls].mx>tr[rs].mx){
            tr[u].mx=tr[ls].mx;
            tr[u].mxpos=tr[ls].mxpos;
        }
        else{
            tr[u].mx=tr[rs].mx;
            tr[u].mxpos=tr[rs].mxpos;
        }
    }

    void pushdown(int u){
        if(tr[u].add){
            tr[ls].mx+=tr[u].add;
            tr[ls].add+=tr[u].add;
            tr[rs].mx+=tr[u].add;
            tr[rs].add+=tr[u].add;
            tr[u].add=0;
        }
    }

    void build(int u,int l,int r){
        tr[u]={l,r,0,0,0};
        if(l==r){
            tr[u].mxpos=l;
            return;
        }
        int mid=(l+r)/2;
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(u);
    }

    void modify(int u,int l,int r,int val){
        if(tr[u].l>=l&&tr[u].r<=r){
            tr[u].mx+=val;
            tr[u].add+=val;
            return ;
        }
        int mid=(tr[u].l+tr[u].r)/2;
        pushdown(u);
        if(l<=mid){
            modify(ls,l,r,val);
        }
        if(r>=mid+1){
            modify(rs,l,r,val);
        }
        pushup(u);
    }

    node ask(int u,int l,int r){
        if(l<=tr[u].l&&tr[u].r<=r){
            return tr[u];
        }
        pushdown(u);
        int mid=(tr[u].l+tr[u].r)/2;
        if(r<=mid)return ask(ls,l,r);
        if(l>mid)return ask(rs,l,r);
        return ask(ls,l,r)+ask(rs,l,r);
    }
}t;
void solve() {
    int n;
    cin>>n;
    vector<int>a(n+1);
    unordered_map<int,vector<int>>pos;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]].push_back(i);
    }
    unordered_map<int,int>last;
    for(int i=n;i>=1;i--){
        if(!last.count(a[i])){
            last[a[i]]=i;
        }
    }
    t.build(1,1,n);

    unordered_map<int,int>mp;
    int ans=0,l=2,r=n;
    for(int i=1;i<=n;i++){
        mp[a[i]]++;
        if(mp[a[i]]==1){
            auto it=upper_bound(pos[a[i]].begin(),pos[a[i]].end(),i);
            if(it!=pos[a[i]].end()){
                int nxt=*it;
                if(nxt+1<=last[a[i]])t.modify(1,nxt+1,last[a[i]],1);
            }
            auto res=t.tr[1];
            if(res.mx>ans){
                ans=res.mx;
                l=i+1,r=res.mxpos;
            }
        }
        else{
            auto it=upper_bound(pos[a[i]].begin(),pos[a[i]].end(),i);
            if(it!=pos[a[i]].end()){
                int nxt=*it;
                if(i+1<=nxt)t.modify(1,i+1,nxt,-1);
            }
            auto res=t.tr[1];
            if(res.mx>ans){
                ans=res.mx;
                l=i+1,r=res.mxpos;
            }
        }
    }
    cout<<ans<<'\n';
    cout<<l<<' '<<r<<'\n';
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; cin >> T;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

K

缩点 树形背包

给一棵有向图树，把一些路径的终点和起点之间连边，也就是创造了一些环。

然后定义神奇集合：这个集合里的所有点能到的所有点，必须都在这个集合里。神奇集合的权值就是所有点的点权和，求有多少种不同的神奇集合权值

有向图有环，先考虑缩点。由于缩之前是一棵树，缩点后也是一棵树（从起点所在强连通分量出发，可以到其它所有点，这个性质连边成环也不会破坏）

然后在这个新图上，一棵子树是一个神奇集合，多个不相交的子树也是神奇集合。所以问的就是所有不相交的子树构成的集合，的不同权值个数。

显然一个树的答案可以从子树合并来，考虑树形，表示为根的子树，权值和为的神奇集合是否存在。

合并时，虽然可以从每一棵子树里选一个子树，构成集合，但这样太麻烦，可以枚举子树，把枚举到的子树合并到根节点里，然后每次看成子树和根节点树，两棵树的合并。然后子树有一个权值的集合，根节点有个权值的集合，那么合并后就有个的集合，仔细看的话，这其实就是背包的转移，根节点看成背包数组，枚举的子树看成新加的一个东西。

这东西其实就是树形背包。唯一的问题是，朴素实现，枚举两个集合权值时，都会枚举到权值值域的上界，这样复杂度炸了。但树形背包告诉我们，实际上只用枚举到子树大小，这样可以实现。

这里是个小变形，传统的树形背包，统计的一般就是点数，或者不超过点数的一个东西，背包值域不会超过子树大小，因为一个子树里的点全产生贡献，也才子树大小个元素。但这里每个点有点权，并且我们维护的是个点权和，看似不能用树形背包来分析了，但这里保证了点权和是的，也就是和点数同阶的，那我们可以把一个点权的点看成个点，最后还是可以用一般的树形背包来分析复杂度，仍然是的复杂度

PS:这里说一下树形背包的实现细节，每个子树的大小需要累加到根节点子树的大小，但需要先转移，再累加，这样能严格保证任何时候枚举的上界，都是实际的子树大小，也就是最小的上界，这样复杂度才是对的，否则会退化。

也就是这样是不行的

void dfs(int u){
    f[u][0]=1;
    for(int v:b[u]){
        dfs(v);
        ww[u]+=ww[v];
        for(int i=ww[u];i>=0;i--){
            if(f[u][i]){
                for(int j=ww[v];j>=0;j--){
//                  cout<<i<<' '<<j<<' '<<f[v][j]<<'\n';
                    f[u][i+j]|=f[v][j];
                }   
            }
        }
    }
    f[u][ww[u]]=1;
}

这样才是对的

void dfs(int u){
    f[u][0]=1;
    for(int v:b[u]){
        dfs(v);
        for(int i=ww[u];i>=0;i--){
            if(f[u][i]){
                for(int j=ww[v];j>=0;j--){
//                  cout<<i<<' '<<j<<' '<<f[v][j]<<'\n';
                    f[u][i+j]|=f[v][j];
                }   
            }
        }
        ww[u]+=ww[v];
    }
    f[u][ww[u]]=1;
}

然后本题实现还有一点需要注意，就是一个根节点x，和一个x的不是儿子的子孙点为根的子树，是不能构成一个神奇集合的，所以我们不能在前赋初始值，这样会让根和所有子树都形成贡献，会包括这种不合法的情况。我们把加入贡献，只能在所有子树的dp都结束之后，把x为根的整个子树计入贡献。

也就是这样是不行的

void dfs(int u){
    f[u][0]=1
    f[u][ww[u]]=1;
    for(int v:b[u]){
        dfs(v);
        for(int i=ww[u];i>=0;i--){
            if(f[u][i]){
                for(int j=ww[v];j>=0;j--){
//                  cout<<i<<' '<<j<<' '<<f[v][j]<<'\n';
                    f[u][i+j]|=f[v][j];
                }   
            }
        }
        ww[u]+=ww[v];
    }
}

这样才是对的

void dfs(int u){
    f[u][0]=1;
    for(int v:b[u]){
        dfs(v);
        for(int i=ww[u];i>=0;i--){
            if(f[u][i]){
                for(int j=ww[v];j>=0;j--){
//                  cout<<i<<' '<<j<<' '<<f[v][j]<<'\n';
                    f[u][i+j]|=f[v][j];
                }   
            }
        }
        ww[u]+=ww[v];
    }
    f[u][ww[u]]=1;
}

缩点部分不谈，写的很简单，也就是配合栈即可找到所有强连通分量，每个强连通分量缩成一个点

#include <bits/stdc++.h>
#define int long long


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 1e4 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;

int in[N],dfn[N],co[N],low[N],s[N],ind[N],top,cnt,tot;
vector<int>a[N],b[N];
inline void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    s[++top]=x;
    ind[x]=1;
    for(int v:a[x]){
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(ind[v]){
            low[x]=min(low[x],low[v]);
        }
    }
    if(low[x]==dfn[x]){
        ++tot;
        while(1){
            int X=s[top--];
            co[X]=tot;
            ind[X]=0;
            if(!(x^X)){
                break;
            }
        }
    }
}
bool f[N][N];
int w[N],ww[N];
void dfs(int u){
    f[u][0]=1;
    for(int v:b[u]){
        dfs(v);
        for(int i=ww[u];i>=0;i--){
        	if(f[u][i]){
				for(int j=ww[v];j>=0;j--){
//					cout<<i<<' '<<j<<' '<<f[v][j]<<'\n';
					f[u][i+j]|=f[v][j];
				}	
        	}
		}
		ww[u]+=ww[v];
    }
    f[u][ww[u]]=1;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
    }
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    for(int i=1;i<=n;i++){
        ww[co[i]]+=w[i];
//         cout<<co[i]<<' ';
        for(int v:a[i]){
            if(co[i]^co[v]){
                b[co[i]].push_back(co[v]);
                in[co[v]]++;
            }
        }
    }
    int rt=-1;
    for(int i=1;i<=tot;i++){
//         cout<<i<<":";
//         for(int v:b[i]){
//             cout<<v<<' ';
//         }
//         cout<<'\n';
//        cout<<ww[i]<<' '<<in[i]<<'\n';
        if(!in[i]){
            rt=i;
        }
    }
    dfs(rt);
    int ans=0;
    for(int i=0;i<=ww[rt];i++){
//    	cout<<f[rt][i]<<' ';
		if(f[rt][i]){
			ans++;
		}
	}
	cout<<ans<<'\n';
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; 
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}