安全
看完题，好，先打一个枚举删边的暴力dp，然后发现不会优化。然后忽然发了大样例，发现挂了，再读一下题，发现删个
的边啊，最开始又不知道...
考虑到一个安全的放置一定得有4个边，像这样
发现内侧边可以和别的外侧边公用之类的，考虑把这个当做状态进行dp
先做一个(y)轴的扫描线，把这样的四元组((l_2,l_1,r_1,r_2))(从左至右)状态都找出来。
可以发现，每次加入一条线的时候，至多产生4个这样的4元组，那么四元组的状态不会超过(4n)
考虑(dp_i)表示(i)号四元组做最左边的坦克时的最大答案，那么有转移
[dp_i=max_j{dp_j|l_1(j)ge r_2(i)land l_2(j)ge r_1(i)}+1
]
对后面的限制条件，一维排序，一维在树状数组里面维护一下就可以了
Code:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
const int N=1e6+5;
using std::max;
template <class T>
void read(T &x)
{
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
struct koito_yuu
{
int x,l,r;
}yuu[N];
int dx[N],dy[N],n,m,k,dp[N<<1];
struct BEE
{
int op,x,p;
BEE(){}
BEE(int Op,int X,int P){op=Op,x=X,p=P;}
bool friend operator <(BEE a,BEE b){return a.p==b.p?a.op>b.op:a.p<b.p;}
}bee[N];
std::set <int> s;
std::set <int>::iterator it;
struct node
{
int l2,l1,r1,r2;
node(){}
node(int L2,int L1,int R1,int R2){l2=L2,l1=L1,r1=R1,r2=R2;}
bool friend operator <(node a,node b){return a.r2>b.r2;}
}yuy[N<<1];
struct mea
{
int l1,id;
mea(){}
mea(int L1,int Id){l1=L1,id=Id;}
bool friend operator <(mea a,mea b){return a.l1<b.l1;}
};
std::priority_queue <mea> q;
int mx[N<<1];
void ins(int x,int d)
{
while(x<=k) mx[x]=max(mx[x],d),x+=x&-x;
}
int qry(int x)
{
int ret=0;
while(x) ret=max(ret,mx[x]),x-=x&-x;
return ret;
}
int main()
{
freopen("safe.in","r",stdin);
freopen("safe.out","w",stdout);
read(n);
dx[++dx[0]]=-1,dx[++dx[0]]=1e9+1;
dx[++dx[0]]=-2,dx[++dx[0]]=1e9+2;
for(int i=1;i<=n;i++)
{
read(yuu[i].x),read(yuu[i].l),read(yuu[i].r);
dx[++dx[0]]=yuu[i].x;
dy[++dy[0]]=yuu[i].l;
dy[++dy[0]]=yuu[i].r;
}
std::sort(dx+1,dx+1+dx[0]);
dx[0]=std::unique(dx+1,dx+1+dx[0])-dx-1;
std::sort(dy+1,dy+1+dy[0]);
dy[0]=std::unique(dy+1,dy+1+dy[0])-dy-1;
for(int i=1;i<=n;i++)
{
yuu[i].x=std::lower_bound(dx+1,dx+1+dx[0],yuu[i].x)-dx;
yuu[i].l=std::lower_bound(dy+1,dy+1+dy[0],yuu[i].l)-dy;
yuu[i].r=std::lower_bound(dy+1,dy+1+dy[0],yuu[i].r)-dy;
bee[++m]=BEE(1,yuu[i].x,yuu[i].l);
bee[++m]=BEE(0,yuu[i].x,yuu[i].r);
}
std::sort(bee+1,bee+1+m);
s.insert(1),s.insert(dx[0]);
s.insert(2),s.insert(dx[0]-1);
for(int i=1;i<=m;i++)
{
if(bee[i].op)//add
{
int p1,p2,p3,p4,p5,p6;
p1=p2=p3=p4=p5=p6=0;
it=s.lower_bound(bee[i].x);
p4=*it;
it++;
p5=*it;
it++;
if(it!=s.end()) p6=*it;
it=s.lower_bound(bee[i].x);
it--;
p3=*it;
it--;
p2=*it;
if(it!=s.begin()) --it,p1=*it;
if(p1) yuy[++k]=node(p1,p2,p3,bee[i].x);
yuy[++k]=node(p2,p3,bee[i].x,p4);
yuy[++k]=node(p3,bee[i].x,p4,p5);
if(p6) yuy[++k]=node(bee[i].x,p4,p5,p6);
s.insert(bee[i].x);
}
else s.erase(bee[i].x);
}
std::sort(yuy+1,yuy+1+k);//按r2排列
int ans=1;
for(int i=1;i<=k;i++)
{
while(!q.empty()&&yuy[i].r2<=q.top().l1)
{
int id=q.top().id;
q.pop();
int p=dx[0]+1-yuy[id].l2;
ins(p,dp[id]);
}
dp[i]=qry(dx[0]+1-yuy[i].r1)+1;
ans=max(ans,dp[i]);
q.push(mea(yuy[i].l1,i));
}
printf("%d
",ans);
return 0;
}
2019.3.24