P3740 [HAOI2014] 贴海报 题解

P3740 [HAOI2014] 贴海报 题解

思路

我们模拟一下贴海报的过程，先把 $x\sim y$的数字全部变成 $k$。后面的数字可以覆盖前面的数字。 如果for循环枚举的话是会超时的，我们考虑用线段树维护区间数字。

那么所有操作结束后如果当前区间还有当前数字，$ans++$。
那么这么判断呢？
也就是pushup怎么做？

求最小值最好了。因为每个区间的最小值只能是当前数字，因为当前区间已经被当前数字全部覆盖了。

代码

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lhs printf("\n");
#define sync std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
using namespace std;
const int N=3e5+10;
const int M=2021;
const int inf=0x3f3f3f3f;
map<int,int> mp;
int n,m;
int num[N],len1; 
int ans;
int minn[N];
int lazy[N];
struct node
{int x,y;
}a[N]; 
bool cmp(node xx,node yy)
{return xx.x<yy.x;
}
void pushdown(int id,int l,int r)
{if(lazy[id]){int mid=(l+r)/2;minn[id*2]=lazy[id];lazy[id*2]=lazy[id];minn[id*2+1]=lazy[id];lazy[id*2+1]=lazy[id];lazy[id]=0;}
}
void pushup(int id)
{minn[id]=min(minn[id*2],minn[id*2+1]);
}
void change(int id,int l,int r,int x,int y,int z)
{if(x<=l and r<=y){minn[id]=z;lazy[id]=z;return;}int mid=(l+r)/2;pushdown(id,l,r);if(x<=mid){change(id*2,l,mid,x,y,z); }if(mid+1<=y){change(id*2+1,mid+1,r,x,y,z);} pushup(id);
} 
int query(int id,int l,int r,int x,int y)
{if(x<=l and r<=y){return minn[id];}int ans=inf;int mid=(l+r)/2;pushdown(id,l,r);if(x<=mid){ans=min(ans,query(id*2,l,mid,x,y));}if(mid+1<=y){ans=min(ans,query(id*2+1,mid+1,r,x,y));}return ans;
}
int main()
{cin>>m>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y; len1++;num[len1]=a[i].x;len1++;num[len1]=a[i].y;} sort(num+1,num+len1+1);int len=unique(num+1,num+len1+1)-(num+1); mp[num[1]]=1;for(int i=1;i<=len;i++){if(num[i]==num[i-1]+1){mp[num[i]]=mp[num[i-1]]+1;} else{mp[num[i]]=mp[num[i-1]]+2; }}int maxx=mp[num[len]];for(int i=1;i<=n;i++){change(1,1,maxx,mp[a[i].x],mp[a[i].y],i);} for(int i=1;i<=n;i++){if(query(1,1,maxx,mp[a[i].x],mp[a[i].y]) ==i){ans++;}}cout<<ans;return 0;
}

AC记录

附上封面(