【1】底边固定的矩形面积交
这是我第一次不知道知识点的时候，瞎用区间最大最小值，做的面积交
还挺快
#include<cstdio> #include<cstdlib> #include<algorithm> #define lnt long long using namespace std; int n; const int N=1e9+3,M=40003; struct node { int x,id,pos; bool operator < (const node & o ) const { return x<o.x; } }ask[M<<1]; int tot,ll[M][2],h[M]; int td[M][2],d[M<<1]; int root,cnt; int ls[M<<2],rs[M<<2],len[M<<2]; int laz[M<<2],mn[M<<2],mx[M<<2]; void updata(int rt) { mn[rt]=min(mn[ls[rt]],mn[rs[rt]]), mx[rt]=max(mx[ls[rt]],mx[rs[rt]]); } void build(int &rt,int l,int r) { rt=++cnt; if(l==r) { len[rt]=d[l+1]-d[l]; return ; } int mid=(l+r)>>1; build(ls[rt],l,mid); build(rs[rt],mid+1,r); len[rt]=len[ls[rt]]+len[rs[rt]]; updata(rt); } void push_down(int rt) { mn[ls[rt]]=mx[ls[rt]]=laz[ls[rt]]=laz[rt]; mn[rs[rt]]=mx[rs[rt]]=laz[rs[rt]]=laz[rt]; laz[rt]=0; } bool change(int rt,int l,int r,int ql,int qr,int h) { if(mn[rt]>=h ) return false; if(ql<=l && r<=qr && mx[rt]<=h ) { mx[rt]=laz[rt]=mn[rt]=h; return true; } if(l==r) return false; if(laz[rt] ) push_down(rt); int mid=(l+r)>>1; bool cg=false; if(ql<=mid) cg|=change(ls[rt],l,mid,ql,qr,h); if(qr> mid) cg|=change(rs[rt],mid+1,r,ql,qr,h); if(cg ) updata(rt); } lnt query(int rt,int l,int r) { if(mx[rt]==mn[rt]) return 1LL*len[rt]*mx[rt]; if(laz[rt] ) push_down(rt); int mid=(l+r)>>1; lnt ans=query(ls[rt],l,mid) ; return ans+query(rs[rt],mid+1,r); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&ll[i][0],&ll[i][1],&h[i]); if(ll[i][0] <= ll[i][1]) { ask[++tot].x =ll[i][0],ask[tot].id =i,ask[tot].pos =0; ask[++tot].x =ll[i][1],ask[tot].id =i,ask[tot].pos =1; } } sort(ask+1,ask+tot+1); int nn=0; for(int i=1;i<=tot;i++) if(ask[i].x ==ask[i-1].x ) ll[ask[i].id ][ask[i].pos ]=ll[ask[i-1].id ][ask[i-1].pos ]; else { d[++nn]=ll[ask[i].id ][ask[i].pos ] ; ll[ask[i].id ][ask[i].pos ]=nn ; } d[nn+1]=d[nn]; build(root,1,nn); for(int i=1;i<=n;i++) if(ll[i][0] <= ll[i][1] ) change(root,1,nn,ll[i][0],ll[i][1]-1,h[i]); printf("%lld ",query(root,1,nn)); return 0; }
【2】矩形周长和
（1）未离散版
USACO picture
我调了一下午......所以就没有离散版了
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n; const int N=5003,M=20003; int cnt; struct node { int h,l,r,w; bool operator < (const node & o ) const { return h!=o.h ?h<o.h :w>o.w ; } }d[N<<2]; int root,tot,ls[M<<1],rs[M<<1]; int tm[M<<1],len[M<<1],num[M<<1];//这里的tm其实就是laz标记，只不过有很多次 bool fl[M<<1],fr[M<<1]; void build(int &rt,int l,int r) { rt=++tot; if(l==r ) return ; int mid=(l+r)>>1; build(ls[rt],l,mid),build(rs[rt],mid+1,r); } void updata(int rt) { len[rt]=len[ls[rt]]+len[rs[rt]]; num[rt]=num[ls[rt]]+num[rs[rt]]- (fr[ls[rt]]&fl[rs[rt]]); fl[rt]=fl[ls[rt]],fr[rt]=fr[rs[rt]]; } int ql,qr,v; void change(int rt,int l,int r) { if(ql<=l && r<=qr ) { tm[rt]+=v; if(tm[rt] ) len[rt]=r-l+1,num[rt]=1,fl[rt]=fr[rt]=true; else if(l==r ) len[rt]=num[rt]=0,fl[rt]=fr[rt]=false; else updata(rt);//区间覆盖问题 的删除操作，比较复杂 return ; } //因为懒惰标记 对操作没有影响（覆盖于加法不同） //所以修改后面的，再updata就行 int mid=(l+r)>>1; if(ql<=mid ) change(ls[rt],l,mid); if(qr> mid ) change(rs[rt],mid+1,r); if(!tm[rt] ) updata(rt); } int main() { scanf("%d",&n); int x[2],y[2],mny=1<<30,mxy=1<<31; for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&x[0],&y[0],&x[1],&y[1]); y[1]--; mny=min(mny,y[0]),mxy=max(mxy,y[1]); d[++cnt].h =x[0],d[cnt].l =y[0],d[cnt].r =y[1],d[cnt].w = 1; d[++cnt].h =x[1],d[cnt].l =y[0],d[cnt].r =y[1],d[cnt].w =-1; } sort(d+1,d+cnt+1); d[cnt+1].h =d[cnt].h ; build(root,mny,mxy); int ans=0,pre=0; for(int i=1;i<=cnt;i++) { ql=d[i].l ,qr=d[i].r ,v=d[i].w ; change(root,mny,mxy ); // printf("%d %d %d ",ql,qr,v); ans+=abs(len[1]-pre); ans+=(d[i+1].h -d[i].h )*num[1]*2; // printf(" %d %d ",abs(len[1]-pre),(d[i+1].h -d[i].h )*num[1]*2); pre=len[1]; } printf("%d",ans); return 0; }