T1题意
给你N个区间和M个点，问有几个点能有被包含的区间(一个区间和一个点只能用一次)
Solution
典型贪心，按线段右端点排序，然后拿STL随便瞎搞就出来了
Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 200100
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int n,m,d,ans;
struct node{int l,r;
inline void add(){read(l),read(r);}
inline int operator <(const node&oth)const{
return r<oth.r;
}
}e;
vector<node> s;
multiset<int> t;
int main(){
read(n);read(m);
for (int i=1; i<=n; ++i) e.add(),s.push_back(e);
for (int i=1; i<=m; ++i) read(d),t.insert(d);
sort(s.begin(),s.end());
for (int i=0; i<n; ++i){ it=t.lower_bound(s[i].l);
if (it!=t.end()&&*it<=s[i].r)ans++,t.erase(it);
}
wt(ans,'\n');
return 0;
}
T2题意
给你N个点，求拿这N个点构成的树的深度的期望并对P取模(保证P为质数)
Solution
预处理dp[i][j]表⽰i个点的森林，有j个点在第⼀棵树的概率，转移考虑第i个点是否在第⼀棵⼦树中，我们有状态转移⽅程
令f[i][j]表⽰有i个点的树，深度不超过j的概率，g[i][j]表⽰有i个点的森林，深度不超过j的概率，f[i][j]直接从g[i-1][j-1]转移来;g[i][j]考虑枚举第⼀棵树的⼤⼩k，从⼀棵树和⼀个森林转移来，同时还要乘上第⼀棵⼦树⼤⼩为k的概率，我们有状态转移⽅程：
最后只要⽤f[n][j]-f[n][j-1]就可以得到深度为j的树的概率。
Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 250
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
template<typename T> inline void pow(T a,T b,T p,T&ret){
ret=1,a%=p;while(b){if (b&1) (ret*=a)%=p;a=(a*a)%p;b>>=1;}
}
ll n,p,ans,dp1[maxn][maxn],dp2[maxn][maxn],dp3[maxn][maxn],res[maxn],inv[maxn];
inline ll DP2(int x,int y);
inline ll DP1(int x,int y){
if (dp1[x][y]!=-1) return dp1[x][y];
dp1[x][y]=DP2(x-1,y-1);return dp1[x][y];
}
inline ll DP2(int x,int y){
if (y<0) return 0;if (x==0) return 1;
if (dp2[x][y]!=-1) return dp2[x][y];
dp2[x][y]=0;for (int k=1; k<=x; k++)
dp2[x][y]=(dp2[x][y]+((DP1(k,y)*DP2(x-k,y))%p*dp3[x][k])%p)%p;
return dp2[x][y];
}
inline void pre(){
if (n==1) puts("0"),exit(0);inv[1]=1,dp3[1][1]=1;
for (ll i=2; i<=n; ++i) pow(i,p-2,p,inv[i]);
memset(dp1,-1,sizeof dp1);memset(dp2,-1,sizeof dp2);
for (int i=2; i<=n; ++i) for (int j=1; j<=i; ++j)
dp3[i][j]=(((dp3[i-1][j-1]*1ll*(1ll*j-1ll))%p*inv[i])%p+((dp3[i-1][j]*1ll*(1ll*i-1ll*j))%p*inv[i])%p)%p;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
read(n),read(p);pre();
for (int i=2; i<=n; ++i) res[i]=DP1(n,i);res[1]=0;
for (int i=2; i<=n; ++i) ans=(ans+(((res[i]-res[i-1])%p)*i)%p)%p;
wt((ans-1+p)%p,'\n');
return 0;
}
T3题意
给你一棵树，每次将编号在区间[l,r]的点染成黑色(每次染色前每个点都为白色)，求每次染色后黑点的联通块个数。
Solution
二维偏序
对于每个询问，我们只要知道两端点都没被影响到的边的数量，就能很好地算出联通块的个数。
将边按编号排序，将询问按右端点排序，再用树状数组维护左端点。据说能拿主席树写，不会
Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 200100
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
struct node{
int l,r,t,d;
inline void add(){read(l),read(r);}
inline int operator <(const node&oth)const{
return l!=oth.l?l>oth.l:r!=oth.r?r<oth.r:t<oth.t;
}
}t[maxn<<1];
int ans[maxn],tr[maxn],n,q,cnt;
inline void ins(int x){for (; x<=n; x+=lowbit(x)) tr[x]++;}
inline int find(int x){int ret=0;for (; x; x-=lowbit(x)) ret+=tr[x];return ret;}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
read(n),read(q);
for (int i=1; i<n; ++i) t[++cnt].add();
for (int l,r,i=1; i<=q; ++i){
read(l),read(r);ans[i]=r-l+1;++cnt;
t[cnt].l=l,t[cnt].r=r,t[cnt].t=1,t[cnt].d=i;
}
sort(t+1,t+cnt+1);
for (int i=1; i<=cnt; ++i)
if (!t[i].t) ins(t[i].r);
else ans[t[i].d]-=find(t[i].r);
for (int i=1; i<=q; ++i) wt(ans[i],'\n');
return 0;
}
