利用到的是，一条线段，只会出现两次。
那么，显然两次在线段树上遍历的节点是一样的，因此，我们可以直接修改定义，\(sum[cur]\) 表示线段树上的节点被多少条线段遍历到了，如果 \(sum[cur]>0\)，显然 \(cur\) 的贡献即区间长度，否则呢？否则，我们不需要考虑更大的区间，因为更大的区间其一定会在深度更小的点算到，因此只需要将左右儿子的答案加起来即可。
那么，你想，对于一条线段加入、删除，其贡献都是对的，那么对于所有线段而言，显然也是对的了。
https://www.luogu.com.cn/problem/P9478
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=(int)(5e5+5);
struct node {
int pos,l,r,v;
node() {
pos=l=r=0;
}
node(int POS,int L,int R,int V) {
pos=POS; l=L; r=R; v=V;
}
}p[N*2];
struct nodex {
int x,y,xx,yy;
nodex() {
x=y=xx=yy=0;
}
nodex(int X,int Y,int XX,int YY) {
x=X; y=Y; xx=XX; yy=YY;
}
}xie[10];
struct Line {
int op,x,y,xx,yy;
Line() {
op=x=y=xx=yy=0;
}
Line(int OP,int X,int Y,int XX,int YY) {
op=OP; x=X; y=Y; xx=XX; yy=YY;
}
}L[N];
int Ltot;
bool vis[10];
int n,m,q,xtot,tot;
bool xiangli(int l,int r,int cl,int cr) {
if(r<cl) return 1;
if(cr<l) return 1;
return 0;
}
bool cmp(const node &x,const node &y) {
return x.pos==y.pos?x.v>y.v:x.pos<y.pos;
}
int ls[N*52],rs[N*52],len[N*52],sum[N*52],num,rt;
void push_up(int cur,int l,int r) {
if(sum[cur]>0) len[cur]=r-l+1;
else {
len[cur]=0;
if(ls[cur]) len[cur]+=len[ls[cur]];
if(rs[cur]) len[cur]+=len[rs[cur]];
}
}
void upt(int &cur,int l,int r,int cl,int cr,int v) {
if(!cur) cur=++num;
if(cl<=l&&r<=cr) {
sum[cur]+=v;
push_up(cur,l,r);
return ;
}
int mid=(l+r)>>1;
if(cl<=mid) upt(ls[cur],l,mid,cl,cr,v);
if(cr>mid) upt(rs[cur],mid+1,r,cl,cr,v);
push_up(cur,l,r);
}
signed main() {
// freopen("color2.in","r",stdin);
// freopen("color.out","w",stdout);
cin.tie(0); ios::sync_with_stdio(false);
int c; cin>>c;
cin>>n>>m>>q;
for(int i=1;i<=q;i++) {
int op,x,y,xx,yy;
cin>>op>>x>>y>>xx>>yy;
if(op==1) {
L[++Ltot]=Line(op,x,y,xx,yy);
p[++tot]=node(x,y,y,1);
p[++tot]=node(xx+1,y,y,-1);
} else if(op==2) {
L[++Ltot]=Line(op,x,y,xx,yy);
p[++tot]=node(x,y,yy,1);
p[++tot]=node(x+1,y,yy,-1);
} else {
xie[++xtot]=nodex(x,y,xx,yy);
}
}
for(int i=1;i<=5;i++) {
for(int j=2;j<=xtot;j++) {
if(vis[j]) continue ;
for(int k=1;k<j;k++) {
if(vis[k]) continue ;
if(xie[k].y-xie[k].x==xie[j].y-xie[j].x) {
if(!xiangli(xie[k].x,xie[k].xx,xie[j].x,xie[j].xx)) {
vis[j]=1;
xie[k].x=min(xie[k].x,xie[j].x);
xie[k].xx=max(xie[k].xx,xie[j].xx);
xie[k].y=min(xie[k].y,xie[j].y);
xie[k].yy=max(xie[k].yy,xie[j].yy);
}
}
if(vis[j]) break ;
}
}
}
sort(p+1,p+1+tot,cmp);
int ans=0;
for(int i=1;i<tot;i++) {
upt(rt,1,m,p[i].l,p[i].r,p[i].v);
// cout<<len[rt]<<" "<<p[i].pos<<'\n';
ans+=(p[i+1].pos-p[i].pos)*len[rt];
}
for(int i=1;i<=xtot;i++) {
if(vis[i]) {
// cout<<i<<'\n';
continue ;
}
map<int,bool>mp; mp.clear();
int res=xie[i].xx-xie[i].x+1;
// cout<<xie[i].x<<" "<<xie[i].xx<<'\n';
for(int j=1;j<=Ltot;j++) {
if(L[j].op==1) {
int a=L[j].y-xie[i].y+xie[i].x;
if(L[j].x<=a&&a<=L[j].xx&&xie[i].x<=a&&a<=xie[i].xx) {
if(!mp.count(a)) mp[a]=1,--res;
}
} else {
int a=xie[i].y-xie[i].x+L[j].x;
if(L[j].y<=a&&a<=L[j].yy&&xie[i].y<=a&&a<=xie[i].yy) {
if(!mp.count(L[j].x)) mp[L[j].x]=1,--res;
}
}
}
ans+=res;
}
cout<<ans;
return 0;
}