题解：P4348 [CERC2015] Cow Confinement
参考的是这篇题解的思路。
我们先发现
又看到奶牛只能向右向下走，所以答案只能是从右边来的，所以我们想到从右到左扫描线，而线段树中只保留目前这一列的答案信息。
我们来依次分类讨论地图上出现的事物都会怎样影响答案。
栅栏的右边界
如图
此时我们从右往左处理过了红色那一列，正在处理蓝色那一列。
而在蓝色那一列，遇到了黄色框住的栅栏右边界，此时我们思考这对蓝色的那一列的答案有什么影响。
肯定是使得黄色框内部的格子门无法往右走，在栅栏内形成了一个独立的空间。
刚好此时还没有统计此列的花朵所带来的贡献，所以我们放心大胆将栅栏内的格子的答案推平成 0。
栅栏的右边界
如图
我们正在处理红色列时，遇到了栅栏的左边界，思考这会对答案带来什么影响。
首当其冲的，本来规划在栅栏内部的蓝色格子们本来是与外界没有通路的。但是栅栏消失了，他们无法去到栅栏内部了，所以他们只能沿着栅栏往下走，一直走到紫色格子。所以他们能吃到的花数等于紫色格子那里的吃到的花数。
我们发现除了对原规划内的格子有影响外，对于现在这张图，蓝色格子本来不能往下走，但是现在没有栅栏了，所以多了往下走的花数，也就是紫色箭头所在格子的花数。
可是本来即使有栅栏，蓝色格子们也可以走绿色路线吃到黄色格子处的答案。如果按上面说的直接加紫色格子的答案的话，会算重黄色格子的贡献，所以应减去黄色格子的答案。
至于黄色格子的贡献，因为它是栅栏的右下角的右下角所以我们在处理栅栏右边界时应该用 std::map 先把他的答案存起来。
蓝色格子的范围应顶到第一个障碍。
花朵
花朵是简单的，它可以使花朵上面只要不顶到栅栏的所有点答案加一。
奶牛
这是简单的，直接单点查询就行。
综上所述，我们需要维护一个数据结构，他应该支持区间修改，区间推平以及单点查询，他就是线段树。
还有如何查找头上的第一个障碍，维护一个 std::set，里面存的是当前列的障碍下标，每次二分查找。我们遇到右边界就增加两个上下界，左边界就删掉他们就可以了。
代码
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define lc p<<1
#define rc p<<1|1
#define db(x) do{ cerr<<x<<' '; }while(0)
// #define linux
using namespace std;
#ifdef linux
#define getchar getchar_unlocked
#endif
inline ll read(){
ll x=0;int f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void fre(){
freopen("cow.in","r",stdin);
freopen("cow.out","w",stdout);
}
const int N=2000010;
int f,m,n;
set< int > s;//存储当前列的所有障碍的下标
map< pair< int , int > , int >mp;//专门存栅栏的右下角的右下角格子的答案
struct node{
int op;//当前事物的类型
//1为右边界，2为左边界，3为花，4为奶牛
int l;
int r;
//l和r是针对的栅栏的那段区间
int x;
//x是针对的花和奶牛的一个点
int to;
//当op为左边界时，to是对应的右边界的列
//当op是奶牛时，to是对应的答案下标
};
vector< node > a[N];//存储事物
bool cmp(node x,node y){ return x.op<y.op; }
struct Setment{
ll sum,lazy,tag;
#define sum(x) t[x].sum//每个点对应的答案
#define lzy(x) t[x].lazy//区间加的lazytag
#define tag(x) t[x].tag//区间退平的lazytag
}t[N<<2];
ll ans[N];//存储每个牛的答案
namespace SegmentTree{
void pushup(int p){ sum(p)=sum(lc)+sum(rc); }
void pushtag(int tg,int ad,int p,int l,int r){
if(tg!=-1) sum(p)=(r-l+1)*tg,lzy(p)=0;
if(ad) sum(p)+=(r-l+1)*ad;
}
void pushdown(int p,int l,int r){
int mid=(l+r)>>1;
pushtag(tag(p),lzy(p),lc,l,mid);
pushtag(tag(p),lzy(p),rc,mid+1,r);
if(tag(p)!=-1) tag(lc)=tag(rc)=tag(p);
lzy(lc)+=lzy(p); lzy(rc)+=lzy(p);
tag(p)=-1; lzy(p)=0;
}
void build(int p,int l,int r){
tag(p)=-1;
if(l==r){ sum(p)=0; return ; }
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(p);
}
void update(int p,int l,int r,int ql,int qr,int val){
if(ql>qr) return ;
if(ql<=l&&r<=qr){ sum(p)+=(r-l+1)*val; lzy(p)+=val; return ; }
int mid=(l+r)>>1; pushdown(p,l,r);
if(ql<=mid) update(lc,l,mid,ql,qr,val);
if(qr>mid) update(rc,mid+1,r,ql,qr,val);
pushup(p);
}
void tp(int p,int l,int r,int ql,int qr,int val){
if(ql>qr) return ;
if(ql<=l&&r<=qr){ sum(p)=(r-l+1)*val; lzy(p)=0; tag(p)=val; return ; }
int mid=(l+r)>>1; pushdown(p,l,r);
if(ql<=mid) tp(lc,l,mid,ql,qr,val);
if(qr>mid) tp(rc,mid+1,r,ql,qr,val);
pushup(p);
}
ll ask(int p,int l,int r,int x){
if(l>r) return 0;
if(l==r){ return sum(p); }
int mid=(l+r)>>1;
pushdown(p,l,r);
if(x<=mid) return ask(lc,l,mid,x);
else return ask(rc,mid+1,r,x);
}
}
using namespace SegmentTree;//标准线段树
signed main(){
// fre();
build(1,1,1000002);//注意如果这里写1000000会因为边界问题错掉
f=read(); for(int i=1;i<=f;i++){ int x_1=read(),y_1=read(),x_2=read(),y_2=read(); a[y_1-1].push_back(node{2,x_1-1,x_2,0,y_2}); a[y_2].push_back(node{1,x_1-1,x_2,0,0}); }//减一点原因是在此时栅栏才算消失
m=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(); a[y].push_back(node{3,0,0,x,0}); }
n=read(); for(int i=1;i<=n;i++){ int x=read(),y=read(); a[y].push_back(node{4,0,0,x,i}); }
for(int i=1000002;i>=1;i--){
sort(a[i].begin(),a[i].end(),cmp);//按照我们分讨的顺序排序
for(auto tmp:a[i]){
int op=tmp.op,l=tmp.l,r=tmp.r,x=tmp.x,to=tmp.to;
if(op==1){
mp[{i+1,r+1}]=ask(1,1,1000002,r+1);//存那个特殊点
tp(1,1,1000002,l+1,r,0);//区间推平成0
s.insert(l); s.insert(r);//记录障碍
}
else if(op==2){
int ans1=mp[{to+1,r+1}],ans2=ask(1,1,1000002,r+1);
tp(1,1,1000002,l+1,r,ans2);
int loc;
auto pos=s.lower_bound(l);
if(pos==s.begin()) loc=0;
else loc=*prev(pos);
update(1,1,1000002,loc+1,l,ans2-ans1);
s.erase(r); s.erase(l);
}
else if(op==3){
int loc;
auto pos=s.lower_bound(x);
if(pos==s.begin()) loc=0;
else loc=*prev(pos);
update(1,1,1000002,loc+1,x,1);
}
else{
ans[to]=ask(1,1,1000002,x);
}
}
}
for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
return 0;
}