题意：
在一块长方形蛋糕上切若干刀，每一刀都是从长方形某条边开始，垂直于这条边，但不切到对边，求把长方形切成了多少块。
题解：
块数=交点数+1
因为对于每个交点，唯一且不重复地对应着一块蛋糕。
就是产生这个交点的相互垂直的两刀，以及这两刀分别上次经过的刀痕或边缘，这四条边确定的长方形。
则问题转化成了求平面上，若干条平行于坐标轴的直线共有几个交点。
离散化后，记录横线的左右端点，竖线的上下端点，枚举横坐标，用树状数组记录这个横坐标上每一个点是否有横线经过。
求某条竖线与几条横线相交，就是在求区间和。
#include<iostream> #include<algorithm> #include<vector> #include<cstring> using namespace std; int countx,county; int tree[100005]; int lowbit(int x){ return x&(-x); } void add(int t,int p){//对x位置增加p； while(t<=county){ tree[t]+=p; t+=lowbit(t); } } int getsum(int t){//1-x的和 ； int res=0; while(t>0){ res+=tree[t]; t=t-lowbit(t); } return res; } int x[100005],y[100005],xx[100005],yy[100005]; char c[100005]; vector<int> ll[100005],rr[100005]; int uu[100005],dd[100005]; int main(){ int t; scanf("%d",&t); while(t--){ int n,m,k; scanf("%d %d %d",&n,&m,&k); for(int i=1;i<=k;i++){ scanf("%d %d %c",&x[i],&y[i],&c[i]); xx[i]=x[i]; yy[i]=y[i]; } sort(xx+1,xx+k+1); sort(yy+1,yy+k+1); countx=unique(xx+1,xx+1+k)-1-xx; county=unique(yy+1,yy+1+k)-1-yy; for(int i=0;i<=countx;i++){ uu[i]=dd[i]=0; ll[i].clear();rr[i].clear(); } for(int i=1;i<=k;i++){ x[i]=lower_bound(xx+1,xx+countx+1,x[i])-xx; y[i]=lower_bound(yy+1,yy+county+1,y[i])-yy; if(c[i]=='U'){ uu[x[i]]=county; dd[x[i]]=y[i]; } if(c[i]=='D'){ uu[x[i]]=y[i]; dd[x[i]]=1; } if(c[i]=='L'){ ll[0].push_back(y[i]); rr[x[i]].push_back(y[i]); } if(c[i]=='R'){ ll[x[i]].push_back(y[i]); } } int ans=0; memset(tree,0,sizeof tree); for(int i=0;i<=countx;i++){ for(int j=0;j<ll[i].size();j++){ add(ll[i][j],1); } // for(int i=1;i<=county;i++){ // printf("%d ",getsum(i)-getsum(i-1)); // } // printf(" "); // printf("%d %d ",uu[i],dd[i]); ans+=getsum(uu[i])-getsum(dd[i]-1); for(int j=0;j<rr[i].size();j++){ add(rr[i][j],-1); } } printf("%d ",ans+1); } return 0; }
PS：离散化的时间复杂度是O(nlogn)，为了保证常数效率和代码整洁，应使用sort，unique和lower_bound三个标准函数