题解 P5464 【缩小社交圈】
Fading
2019-07-14 21:22:18
疯掉了，这道题看了大概$20$分种就有思路，但是调起来就是$1$个半小时。
原来是自己考虑太少了，对拍了$30$分种才出错（鬼知道为什么）
深深感到我的信息天赋为$\huge 0$。
### 约定
$x_i,y_i$分别表示第$i$个区间的左右端点。
### 算法$1$:
我会状压！
期望得分：$20$分。
### 算法$2$:
我们先对所有区间按照右端点进行排序。
然后发现连边就成了这样：
如果我们按序编号，就变成了这样：
发现了什么？
#### 如果$l,r(l<r)$之间有边，那么$[l,r-1]$之间的点均与$r$有边。
这就是我们要排序的原因，之后我们可以直接开始$dp$了！
#### 情况$1$
发现排序以后，假设我们$dp$到了第$i$条线段，那么我们枚举$1\sim i-1$的线段$j$。
我们发现，如果$j\cap i=\varnothing(y_j<x_i)$，那么没法转移（不能为森林）
如果$j\cap i \not=j\ (x_j<x_i)$，如图：
那么我们可以选择$j$，但是，如果选了$j$，有一些边，比如打上橙色叉叉的边，就不能选。为什么呢？这样会出现三元环！
所以我们不能单纯的用$f_i$表示前$i$个的方案数，我们可以考虑设$f_{i,j}$表示选择$i$，且上一个选择$j$的方案数。
这样，如果选择了$y_j\geq x_i$的$j$，所有满足$y_k\geq x_i$的边都不可以选。
那么我们有转移方程式：
$$f_{i,j}=\sum_{k=0,y_k<x_i}^{i-1}f_{j,k}\ \ (y_j\geq x_i,x_j<x_i)$$
#### 情况$2$
傻逼的我忘记了这种情况^_^，拍了很久才发现。
如果$j\cap i =j\ (x_j\geq x_i)$，如图
$j$被$i$包含了。我们可以选择$j$，但是...
情况变得棘手很多。
发现选择$i,j$以及打上绿色勾勾的边是可以构成一棵树的，而选择打上橙色叉叉的则不行（环！）...
那么，仿佛我们又可以转移了！
我们选择了$j$以后，就不可以选择$y_k\geq x_j$的$j!!!$
好了，我们又可以得到方程了。
$$f_{i,j}=\sum_{k=0,y_k<x_j}^{i-1}f_{j,k}\ \ (y_j\geq x_i,x_j>x_i)$$
对吗？
#### 错了！
这样子$f_{j,k}$不都等于$0$了吗？
其实此时假设选择$k$，那么对于所有的$f_{i,k}$，再接上一个$j$不会有问题。
所以我们的方程应该是这样：
$$f_{i,j}=\sum_{k=0,y_k<x_j}^{i-1}f_{i,k}\ \ (y_j\geq x_i,x_j>x_i)$$
那么我们分两类情况讨论就好了！
#### 边界
$f_i[0]=1$
#### 最终答案
就是
$$\sum_{i=1}^n\sum_{j=0}^{i-1}f_{i,j}$$
期望得分：$60$分。
### 算法$3$:
看看我们的方程式：
$$f_{i,j}=\sum_{k=0,y_k<x_i}^{i-1}f_{j,k}\ \ (y_j\geq x_i,x_j<x_i)$$
$$f_{i,j}=\sum_{k=0,y_k<x_j}^{i-1}f_{i,k}\ \ (y_j\geq x_i,x_j>x_i)$$
是不是可以树状数组优化呢？
那么这道题就做完了。
时间复杂度$O(n^2log_2n)$
期望得分：$100$分。
代码：
```cpp
#include<bits/stdc++.h>
#define ll long long
#define ljc 1000000007
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
#endif
inline ll read(){
register ll x=0,f=1;char ch=gc();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
return (f==1)?x:-x;
}
int f[4011][4011],n,m,L[4021];
struct que{
int x,y;
}x[4011];
inline bool cmp(que a,que b){
if (a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
struct tree{
int tr[4021];
inline void add(int a,int b){
a++;
for (;a<=4001;a+=a&-a) tr[a]=(tr[a]+b)%ljc;
}
inline int query(int a){
int ans=0;
a++;
for (;a;a-=a&-a) ans=(ans+tr[a])%ljc;
return ans;
}
}tr[4021];
signed main(){
n=read();
for (int i=1;i<=n;i++){
x[i].x=read(),x[i].y=read();
}
sort(x+1,x+1+n,cmp);
for (int i=2;i<=n;i++){
int lb=1,rb=i,ans=-1;
while (lb<=rb){
int mid=lb+rb>>1;
if (x[mid].y<x[i].x) lb=mid+1;
else ans=mid,rb=mid-1;
}
L[i]=ans;//卡常用的，预处理第一个满足条件的点
}
for (int i=1;i<=n;i++) f[i][0]=1,tr[i].add(0,1);
for (int i=2;i<=n;i++){
for (int j=L[i];j<i;j++){
if (x[i].x<=x[j].x){
f[i][j]=tr[i].query(x[j].x-1);
}else{
f[i][j]=tr[j].query(x[i].x-1);
}
tr[i].add(x[j].y,f[i][j]);
}
}
int ans=0;
for (int i=1;i<=n;i++){
for (int j=0;j<i;j++){
ans=(ans+f[i][j])%ljc;
}
}
printf("%d\n",ans);
return 0;
}
```
### 算法$4$：
发现我们对区间进行了排序，那么每一次加入树状数组的点都是递增的。
所以我们可以用前缀和优化时间复杂度。
开一个变量，更新前缀和的时候扫一遍即可。
时间复杂度$O(n^2)$
期望得分：$100$分
细节见代码，非常多。
~~也就比树状数组快了100ms~~
```cpp
#include<bits/stdc++.h>
#define ll long long
#define ljc 1000000007
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
#endif
inline ll read(){
register ll x=0,f=1;char ch=gc();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
return (f==1)?x:-x;
}
int f[4011][4011],n,m,L[4021];
struct que{
int x,y;
}x[4011];
inline bool cmp(que a,que b){
if (a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
int sum[4021][4021];
signed main(){
n=read();
for (int i=1;i<=n;i++){
x[i].x=read(),x[i].y=read();
}
sort(x+1,x+1+n,cmp);
for (int i=2;i<=n;i++){
int lb=1,rb=i,ans=-1;
while (lb<=rb){
int mid=lb+rb>>1;
if (x[mid].y<x[i].x) lb=mid+1;
else ans=mid,rb=mid-1;
}
L[i]=ans;
}
for (int i=1;i<=4000;i++) f[i][0]=1,sum[i][0]=1,sum[1][i]=1;
for (int i=2,las=0;i<=n;i++){
for (las=1;las<=x[L[i]].x;las++){//为第一种情况做准备
sum[i][las]=sum[i][las-1];
}
for (int j=L[i],k;j<i;j++){
if (x[i].x<=x[j].x){
f[i][j]=sum[i][x[j].x-1];
}else{
f[i][j]=sum[j][x[i].x-1];
}
for (k=las;k<=x[j].y;k++){//更新前缀和
sum[i][k]=sum[i][k-1];
}
sum[i][k-1]=(sum[i][k-1]+f[i][j])%ljc;
for (;k<=x[j+1].x-1;k++){//为下一次做准备
sum[i][k]=sum[i][k-1];
}
las=k;
}
for (;las<=4000;las++){//更新完所有前缀和
sum[i][las]=sum[i][las-1];
}
}
int ans=0;
for (int i=1;i<=n;i++){
for (int j=0;j<i;j++){
ans=(ans+f[i][j])%ljc;
}
}
printf("%d\n",ans);
return 0;
}
```