gym 101480 Problem C: Cow Confinement 题解
算法知识：dp+扫描线。
从下往上扫描，维护一个线段树就可以了。线段树支持区间清零，区间加和单点查询。
Warning：扫描线预处理排序的部分需要注意先后顺序。
/*
{
######################
# Author #
# Gary #
# 2020 #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<'0'||ch>'9'){
// ch=getchar();
// }
// while(ch>='0'&&ch<='9'){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int N=1<<20;
bool asi[N+N];//是否都设置成0
int delta[N+N];//增量
void pd(int now){
if(asi[now]){
asi[now<<1]=asi[now<<1|1]=1;
delta[now<<1]=delta[now<<1|1]=delta[now];
}
else{
delta[now<<1]+=delta[now];
delta[now<<1|1]+=delta[now];
}
asi[now]=0;
delta[now]=0;
}
void Assign(int a,int b,int now=1,int l=1,int r=N+1){
if(r<=a||l>=b){
return;
}
if(r<=b&&l>=a){
delta[now]=0;
asi[now]=1;
return ;
}
pd(now);
int mid=(l+r)>>1;
Assign(a,b,now<<1,l,mid);
Assign(a,b,now<<1|1,mid,r);
}
void Add(int a,int b,int val,int now=1,int l=1,int r=N+1){
if(r<=a||l>=b) return ;
if(r<=b&&l>=a){
delta[now]+=val;
return;
}
pd(now);
int mid=(l+r)>>1;
Add(a,b,val,now<<1,l,mid);
Add(a,b,val,now<<1|1,mid,r);
}
int query(int pos){
pos+=N-1;
int rest=0;
while(pos){
if(asi[pos]){
rest=0;
}
rest+=delta[pos];
pos>>=1;
}
return rest;
}
int answer[N],tmpanswer[N]/*记录每一个fence右下角的答案*/;
int f,m,n;
set<int> wall;
struct Event{
int ty;//种类
/*
1. 上边界
2. 下边界
3. 花
4. 牛
*/
int r,c,len,id;
Event(){}
Event(int T,int X,int Y){
ty=T;
r=X;
c=Y;
}
Event(int T,int X,int Y,int L,int I){
ty=T;
r=X;
c=Y;
len=L;
id=I;
}
bool operator < (Event oth){
if(r!=oth.r) return r>oth.r;
if((!(ty<=2&&oth.ty<=2))&&ty!=oth.ty) return ty<oth.ty;
return c<oth.c;
}
};
vector<Event> v;
int main(){
scanf("%d",&f);
rb(i,1,f){
int r1,c1,r2,c2;
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
r1--;
v.PB(Event(1,r1,c1,c2-c1+1,i));
v.PB(Event(2,r2,c1,c2-c1+1,i));
}
scanf("%d",&m);
rb(i,1,m){
int r,c;
scanf("%d%d",&r,&c);
v.PB(Event(3,r,c));
}
scanf("%d",&n);
rb(i,1,n){
int r,c;
scanf("%d%d",&r,&c);
v.PB(Event(4,r,c,0,i));
}
sort(ALL(v));
for(int i=0;i<v.size();++i){
int j;
for(j=i;j<v.size()&&v[j].r==v[i].r;++j){
Event Eve=v[j];
if(Eve.ty==1){
Assign(Eve.c,Eve.c+Eve.len);
wall.erase(Eve.c-1);
wall.erase(Eve.c+Eve.len-1);
int tmp=query(Eve.c+Eve.len);
tmp-=tmpanswer[Eve.id];
auto can=wall.lower_bound(Eve.c);
if(can==wall.begin()) Add(1,Eve.c+Eve.len,tmp);
else{
--can;
Add((*can)+1,Eve.c+Eve.len,tmp);
}
Add(Eve.c,Eve.c+Eve.len,tmpanswer[Eve.id]);
}
if(Eve.ty==2){
wall.insert(Eve.c-1);
wall.insert(Eve.c+Eve.len-1);
Assign(Eve.c,Eve.c+Eve.len);
tmpanswer[Eve.id]=query(Eve.c+Eve.len);
}
if(Eve.ty==3){
auto can=wall.lower_bound(Eve.c);
if(can==wall.begin()) Add(1,Eve.c+1,1);
else{
--can;
Add((*can)+1,Eve.c+1,1);
}
}
if(Eve.ty==4){
answer[Eve.id]=query(Eve.c);
}
}
i=j-1;
}
rb(i,1,n) printf("%d
",answer[i]);
return 0;
}/*
4
2 2 8 4
1 9 4 10
6 7 9 9
3 3 7 3
1
2 2 8 4
9
3 4
8 4
11 5
10 7
10 8
9 8
2 8
4 11
9 11
1
1 1
*/