CF1557D Ezzat and Grid
前言
线段树好题一个。
解题思路
我们首先先要对数据进行离散化，这是一个常规套路。
正难则反，我们考虑 dp 。令 (f_i) 表示以 (i) 为结尾，最多可以选择多少行。显然，我们有转移方程：
[f_i=maxlimits_{j<i operatorname{and} g(i,j)} f_j+1
]
其中 (g(i,j)) 为一个布尔函数，表示第 (i,j) 行是否可以相邻。
这显然是一个 (O(n^3)) 级别的算法，我们考虑优化一下，可以用线段树。
我们假设现在考虑已经求出对于 (jin [1,i]) 中的所有 (f_j)，我们线段树维护的是目前，区间所被覆盖的行中 (f_i) 值最大的那一个，这样我们在求解 (f_{i+1}) 时，可以利用线段树上的信息了。
最后答案就是 (n-maxlimits_{i=1}^n f_i)。
求解方案的话，只要记录一下决策点即可。
时间复杂度 (O(nlog n))。线段树帮助我们省去了枚举 (j) 和计算 (g) 函数的时间。
代码
注意有几处等于号一定要有，否则会错。
别问我怎么知道。
22次的提交记录告诉我的
原因的话，是因为可能因为 pushup 操作导致父节点的 (maxx) 值已经正确，但是另外一个子节点无法更新到。
这话很抽象，最好在实践中理解。。。。。
//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int MAXN=3e5+10;
int n,m,len,cnt;
struct segment {
int maxx,lazy;
}s[MAXN<<3];
struct sgm {
int id,l,r;
}sm[MAXN];
int num[MAXN<<1],f[MAXN],g[MAXN];
bool vis[MAXN];
vector<sgm> vec[MAXN];
void pushdown(int l,int r,int p) {
if(l==r) {
return ;
}
int mid=(l+r)>>1;
if(f[s[p].lazy]>=f[s[p<<1].maxx]) {
s[p<<1].maxx=s[p].lazy;
s[p<<1].lazy=s[p].lazy;
}
if(f[s[p].lazy]>=f[s[p<<1|1].maxx]) {
s[p<<1|1].maxx=s[p].lazy;
s[p<<1|1].lazy=s[p].lazy;
}
s[p].lazy=0;
}
segment pushup(segment lft,segment rgt) {
segment ret=s[0];
if(f[lft.maxx]>f[rgt.maxx]) {
ret.maxx=lft.maxx;
}
else {
ret.maxx=rgt.maxx;
}
return ret;
}
void modify(int l,int r,int p,int x,int y,int val) {
if(r<x||y<l) {
return ;
}
pushdown(l,r,p);
if(x<=l&&r<=y) {
if(f[val]>=f[s[p].maxx]) {
//here
s[p].maxx=val;
s[p].lazy=val;
}
return ;
}
int mid=(l+r)>>1;
modify(l,mid,p<<1,x,y,val);
modify(mid+1,r,p<<1|1,x,y,val);
s[p]=pushup(s[p<<1],s[p<<1|1]);
}
segment query(int l,int r,int p,int x,int y) {
if(r<x||y<l) {
return s[0];
}
pushdown(l,r,p);
if(x<=l&&r<=y) {
return s[p];
}
int mid=(l+r)>>1;
return pushup(query(l,mid,p<<1,x,y),query(mid+1,r,p<<1|1,x,y));
}
int get(int x) {
return lower_bound(num+1,num+len+1,x)-num;
}
signed main() {
cin>>n>>m;
for(int i=1;i<=m;i++) {
sm[i].id=read();num[++cnt]=sm[i].l=read();num[++cnt]=sm[i].r=read();
}
sort(num+1,num+cnt+1);
len=unique(num+1,num+cnt+1)-num-1;
for(int i=1;i<=m;i++) {
sm[i].l=get(sm[i].l);
sm[i].r=get(sm[i].r);
vec[sm[i].id].push_back(sm[i]);
}
int tp=0,maxx=0;
for(int i=1;i<=n;i++) {
if(i==6) {
int hhh;
hhh++;
}
segment ans=s[0];
int sz=vec[i].size();
for(int j=0;j<sz;j++) {
ans=pushup(ans,query(1,len,1,vec[i][j].l,vec[i][j].r));
}
f[i]=f[ans.maxx]+1;
g[i]=ans.maxx;
//cout<<f[i]<<" "<<g[i]<<endl;
if(f[i]>maxx) {
maxx=f[i];
tp=i;
}
for(int j=0;j<sz;j++) {
modify(1,len,1,vec[i][j].l,vec[i][j].r,i);
}
}
int ans=n;
while(tp) {
ans--;
vis[tp]=1;
tp=g[tp];
}
cout<<ans<<endl;
for(int i=1;i<=n;i++) {
if(!vis[i]) {
printf("%d ",i);
}
}
return 0;
}