hdu6681 Rikka with Cake(主席树)
题目链接
大意：给你一个矩形区域， ((0,0)−(n,m))，现在有k条直线，每条直线都是从一个点出发到上下左右四个方向之一。
问你这个区域被分成了多少块。
思路：稍微观察即可发现，分成的区域等于直线交点个数+1。
我们对 L,R方向的对纵坐标分开离散化建立主席树（横坐标放一起离散化），然后每次遍历 U,D方向的直线来在主席树上查询。
设当前横坐标为x
方向是U的话，那么L方向上横坐标x大于等于x的都为有效贡献，小于等于x的R方向都有贡献（纵坐标在范围内）。
方向的D的话，那么L方向上横坐标x大于等于x的都为有效贡献，小于等于x的R方向都有贡献（纵坐标在范围内）。
我们查询的时候分别对两个主席树进行查询，每次查询一个合法的纵坐标区间即可。
细节见代码
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 3e5 +11;
int t;
int n,m,k;
struct uzi
{
int a,b;
char c;
}p[N];
int a[N],b[N];
char c[N];
int cmp(uzi l,uzi r){
return l.b<r.b;
}
struct fak{
LL sum;
int l,r;
}T1[N*40],T2[N*40];
int n1,n2;
int t1[N],t2[N];
void up1(int l,int r,int &x,int y,int pos){
T1[++n1]=T1[y];if(pos)T1[n1].sum++;x=n1;
if(l==r)return ;
int mid=l+r>>1;
if(mid>=pos)up1(l,mid,T1[x].l,T1[y].l,pos);
else up1(mid+1,r,T1[x].r,T1[y].r,pos);
}
void up2(int l,int r,int &x,int y,int pos){
T2[++n2]=T2[y];if(pos)T2[n2].sum++;x=n2;
if(l==r)return ;
int mid=l+r>>1;
if(mid>=pos)up2(l,mid,T2[x].l,T2[y].l,pos);
else up2(mid+1,r,T2[x].r,T2[y].r,pos);
}
LL g1(int l,int r,int x,int y,int k){
if(!x&&!y)return 0;
if(r<k)return 0;
if(l>=k)return T1[y].sum-T1[x].sum;;
int mid=l+r>>1;
return g1(l,mid,T1[x].l,T1[y].l,k)+g1(mid+1,r,T1[x].r,T1[y].r,k);
}
LL g2(int l,int r,int x,int y,int k){
if(!x&&!y)return 0;
if(l>k)return 0;
if(r<=k)return (T2[y].sum-T2[x].sum);
int mid=l+r>>1;
return g2(l,mid,T2[x].l,T2[y].l,k)+g2(mid+1,r,T2[x].r,T2[y].r,k);
}
int PA[N],PB[N],La,Lb;
int main(){
ios::sync_with_stdio(false);
for(cin>>t;t;t--){
cin>>n>>m>>k;
n1=n2=0;
La=0;Lb=0;
for(int i=1;i<=k;i++){
cin>>a[i]>>b[i]>>c[i];
p[i]={a[i],b[i],c[i]};
if(c[i]=='L')PA[++La]=b[i];
if(c[i]=='R')PB[++Lb]=b[i];
}
sort(a+1,a+1+k);
int r=unique(a+1,a+1+k)-a-1;
sort(PA+1,PA+1+La);
sort(PB+1,PB+1+Lb);
La=unique(PA+1,PA+1+La)-PA-1;
Lb=unique(PB+1,PB+1+Lb)-PB-1;
for(int i=1;i<=k;i++){
if(c[i]=='L'){
p[i].b=lower_bound(PA+1,PA+1+La,p[i].b)-PA;
}else if(c[i]=='R'){
p[i].b=lower_bound(PB+1,PB+1+Lb,p[i].b)-PB;
}
}
for(int i=1;i<=k;i++)p[i].a=lower_bound(a+1,a+1+r,p[i].a)-a;
sort(p+1,p+1+k,cmp);
for(int i=1;i<=k;i++){
if(p[i].c=='L'){
up1(0,r+1,t1[p[i].b],t1[p[i].b-1],p[i].a);
}else if(p[i].c=='R'){
up2(0,r+1,t2[p[i].b],t2[p[i].b-1],p[i].a);
}
}
up1(0,r+1,t1[La+1],t1[La],0);
up2(0,r+1,t2[Lb+1],t2[Lb],0);
LL A=0;
for(int i=1;i<=k;i++){
if(p[i].c=='U'){
int quL=lower_bound(PA+1,PA+1+La,p[i].b)-PA;
int quR=lower_bound(PB+1,PB+1+Lb,p[i].b)-PB;
A+=g1(0,r+1,t1[quL-1],t1[La+1],p[i].a);
A+=g2(0,r+1,t2[quR-1],t2[Lb+1],p[i].a);
}else if(p[i].c=='D'){
int quL=upper_bound(PA+1,PA+1+La,p[i].b)-PA;
int quR=upper_bound(PB+1,PB+1+Lb,p[i].b)-PB;
quL--;
quR--;
A+=g1(0,r+1,0,t1[quL],p[i].a);
A+=g2(0,r+1,0,t2[quR],p[i].a);
}
}
cout<<A+1<<endl;
}
return 0;
}
