HDU - 6681

题目链接： HDU - 6681

显然这是一个平面图，我们可以根据欧拉公式：V - E + F = 2

假设射线之间交点个数为x，有n条线段。

那么V = 4 + x + 2*n , E = 4 + 2*x + 2*n

所以：F = 2 + E - V = x + 1

所以我们维护交点个数即可。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,M=N*200;
int n,m,k,lc[M],rc[M],lazy[M],cnt,rt; char op[5]; long long res;
struct node{int x,y; char ch;}t[N];
inline void push_down(int p){lazy[lc[p]]+=lazy[p],lazy[rc[p]]+=lazy[p],lazy[p]=0;}
#define mid (l+r>>1)
void change(int &p,int l,int r,int ql,int qr){
    if(l==ql&&r==qr){lazy[p]++; return ;}
    if(!lc[p])    lc[p]=++cnt;    if(!rc[p])    rc[p]=++cnt;
    push_down(p);
    if(qr<=mid)    change(lc[p],l,mid,ql,qr);
    else if(ql>mid)    change(rc[p],mid+1,r,ql,qr);
    else change(lc[p],l,mid,ql,mid),change(rc[p],mid+1,r,mid+1,qr);
}
int ask(int p,int l,int r,int x){
    if(l==r)    return lazy[p];
    if(!lc[p])    lc[p]=++cnt;    if(!rc[p])    rc[p]=++cnt;
    push_down(p);
    if(x<=mid)    return ask(lc[p],l,mid,x);
    else    return ask(rc[p],mid+1,r,x);
}
#undef mid
inline void init(){for(int i=1;i<=cnt;i++) lc[i]=rc[i]=lazy[i]=0; rt=cnt=1;}
inline void calc(){
	init();	sort(t+1,t+1+k,[](node a,node b){return a.y<b.y;});
	for(int i=1;i<=k;i++){
		if(t[i].ch=='L')	change(rt,1,n,1,t[i].x);
		else if(t[i].ch=='R')	change(rt,1,n,t[i].x,n);
		else if(t[i].ch=='D')	res+=ask(rt,1,n,t[i].x);
	}
	init();
	for(int i=k;i>=1;i--){
		if(t[i].ch=='L')	change(rt,1,n,1,t[i].x);
		else if(t[i].ch=='R')	change(rt,1,n,t[i].x,n);
		else if(t[i].ch=='U')	res+=ask(rt,1,n,t[i].x);
	}
	printf("%lldn",res+1);
}
inline void solve(){
    scanf("%d %d %d",&n,&m,&k); res=0; 
    for(int i=1,x,y;i<=k;i++)    scanf("%d %d %s",&x,&y,op),t[i]={x,y,op[0]};
    calc();
}
signed main(){
    int T; cin>>T; while(T--) solve();
    return 0;
}

最后

以上就是舒服钥匙为你收集整理的HDU - 6681的全部内容，希望文章能够帮你解决HDU - 6681所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。