[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\n",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\n",ql,qr,v);
- ans+=abs(len[1]-pre);
- ans+=(d[i+1].h -d[i].h )*num[1]*2;
- // printf("%d %d\n",abs(len[1]-pre),(d[i+1].h -d[i].h )*num[1]*2);
- pre=len[1];
- }
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3274047.html