D
https://www.luogu.com.cn/problem/CF1278D
扫描线判断构成的边是否n-1条，用并查集寻父亲判断会不会构成环
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
set<int>s;
int n,l,r,res,fa[maxn],cnt,R[maxn],book,mp[maxn*2];
struct node{
int pos,id,op;
}A[maxn*2];
bool cmp(node a,node b){return a.pos<b.pos;}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&l,&r);
A[++cnt].op=1,A[cnt].pos=l,A[cnt].id=i;
A[++cnt].op=0,A[cnt].pos=r,A[cnt].id=i;
R[i]=r;
mp[r]=i;
mp[l]=i;
}
sort(A+1,A+1+cnt,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
// for(int i=1;i<=cnt;i++) cout<<A[i].pos<<' ';
for(int i=1;i<=cnt;i++){
if(A[i].op==1){
for(auto it=s.begin();it!=s.end();it++){
if(*it>R[A[i].id]) break;
res++;if(res>=n) break;
int u=getfa(A[i].id),v=getfa(mp[*it]);
// cout<<"U="<<u<<' '<<v<<endl;
if(u==v) book=1;else fa[u]=v;
}
s.insert(R[A[i].id]);
}
else {s.erase(s.find(A[i].pos));}
}
if(res!=n-1) cout<<"NO"<<endl;
else {
if(book) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
C
2n的1 2序列，你在n和n+1之间，你可以往左边往右边吃过去，你需要吃最少的1 2，使得剩余的1 2数量相等。
把2改为-1，这样就可以通过前缀后缀来找得最优值
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
int main(){
int t;
cin>>t;
while(t--){
int s[N]={0};
map<int,int> pos;
int i;
int n;
cin>>n;
pos[0]=0;
for(i=1;i<=2*n;i++){
int a;
cin>>a;
if(a==2)
a=-1;
s[i]=s[i-1]+a;
if(i<=n)
pos[s[i]]=i;
}
int res=2*n;
for(i=n;i<=2*n;i++){
auto it=pos.find(s[i]-s[2*n]);//（-（s[2*n]-s[i]）表示的是后缀的负值）
if(it!=pos.end())
res=min(res,i-it->second);
}
cout<<res<<endl;
}
}
E
给你一棵树，给D题那样出数据。
首先给出下面这样最基础的一棵树
A
/
B C
我们可以只要确定了BC的儿子的左端点，那么A的右端点就可以确认，而他们儿子BC的右端点也是同理，那么我就知道dfs递归处理
也就是一开始A左端点为1，B为2，C为3，那么A右端点为4.但是接下来有个问题提醒一下D题已经说区间如果不是相交而不是内包含就不算一条边），仅仅这样，儿子他们会相交导致他们连边。
例如BC已知2 3，如果B右为5，C右6那就相交了，，利用B的左端点比C的左端点小，且内含不代表连边的特性，我们只需先让C的右端点小于B的右端点就形成内含不形成边。
那么就是A当前节点处理好，进行儿子递归时候我们先让右儿子进行递归，先完成他的右端点，那我们的左儿子的右端点肯定大于他，就可以形成内含。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5;
vector <int> G[N];
int n;
int L[N], R[N];
int tot;
void dfs(int u, int fa) {
for(auto v : G[u]) if(v != fa) {
L[v] = ++tot;
}
R[u] = ++tot;
for(int i = sz(G[u]) - 1; i >= 0; i--) {
int v = G[u][i];
if(v != fa) dfs(v, u);
}
}
void run(){
for(int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
L[1] = ++tot;
dfs(1, 0);
for(int i = 1; i <= n; i++) {
cout << L[i] << ' ' << R[i] << '
';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin >> n) run();
return 0;
}