SD集训divisors
题目大意：给定一个1～n的排列p，求l<=a,b<=r中pa%pb=0的（a，b）数对个数。
思路：离线操作。对于1～n所有数在n以内的约数个数n/1+n/2+n/3+...+n/n=nlogn，那么我们可以保存下所有的这样成倍数的关系，按左端点排序，然后暴力插入。对于查询也是离线的，按左端点排序，对于关系的左边已经在当前左端点左边的就删掉，然后对于右边的统计相应的和就可以了（用树状数组维护）。
用到的排序和扫描线的思想。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxnode 200005 using namespace std; struct use{ int l,r,po; }ask[maxnode]={0},bei[4000005]; int ci[maxnode]={0},pos[maxnode]={0},ai[maxnode]={0},n,ans[maxnode]={0}; int lowbit(int x){return x&-x;} int cmp(const use &x,const use &y){return x.l<y.l;} void add(int x,int y){for (;x<=n;x+=lowbit(x)) ci[x]+=y;} void get(int x,int y){for (;y;y-=lowbit(y)) ans[x]+=ci[y];} int main() { freopen("divisors.in","r",stdin); freopen("divisors.out","w",stdout); int m,i,j,tot=0; scanf("%d%d",&n,&m); for (i=1;i<=n;++i){scanf("%d",&ai[i]);pos[ai[i]]=i;} for (i=1;i<=n;++i) for (j=i;j<=n;j+=i){bei[++tot].l=min(pos[i],pos[j]);bei[tot].r=max(pos[i],pos[j]);} sort(bei+1,bei+tot+1,cmp); for (i=1;i<=tot;++i) add(bei[i].r,1); for (i=1;i<=m;++i) {scanf("%d%d",&ask[i].l,&ask[i].r);ask[i].po=i;} sort(ask+1,ask+m+1,cmp);j=1; for (i=1;i<=m;++i) { while(j<=tot&&bei[j].l<ask[i].l) { add(bei[j].r,-1);++j; } get(ask[i].po,ask[i].r); } for (i=1;i<=m;++i) printf("%d ",ans[i]); }
bzoj4548 小奇的糖果
题目大意：平面内有n个k种颜色的糖果，选某条水平线段上或下的所有糖果，要求不能取出所有颜色，问最多能取多少个。
思路：对于取下面的，按y从小到大，用树状数组维护x坐标为1～i的个数，用动态开点线段树维护每种颜色的位置，对于i这个点，考虑取不到i这种颜色的最大区间就是i纵坐标下面的且在i这种颜色前驱后继之间的部分，统计和就可以了；取上面的一样；取某些直线的情况（这些直线的一边颜色不足k个）；还有取某两个颜色中间的部分（从上到下的糖果都能取）。
注意：中间部分的统计的时候还要算上两边的。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 200005 #define M 4000005 using namespace std; struct use{int x,y,c;}ai[N]; struct tree{int l,r,mn,mx;}tr[M]; int ci[N],cz,tt,rt[N],cc[N],la[N]; int in(){ char ch=getchar();int x=0,f=1; while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x*f;} int cmp(const use&x,const use&y){return (x.y==y.y ? x.x<y.x : x.y<y.y);} int cmp1(const use&x,const use&y){return x.x<y.x;} int lowbit(int x){return x&(-x);} void cins(int x){for (;x<=cz;x+=lowbit(x)) ++cc[x];} int cask(int x){int sm=0;for (;x;x-=lowbit(x)) sm+=cc[x];return sm;} void ins(int &i,int la,int l,int r,int x){ tr[i=++tt]=tr[la]; tr[i].mx=max(tr[i].mx,x); tr[i].mn=min(tr[i].mn,x); if (l==r) return; int mid=(l+r)>>1; if (x<=mid) ins(tr[i].l,tr[la].l,l,mid,x); else ins(tr[i].r,tr[la].r,mid+1,r,x);} int amn(int i,int l,int r,int ll,int rr){ if (!i) return cz+1; if (ll<=l&&r<=rr) return tr[i].mn; int mid=(l+r)>>1;int mn=cz+1; if (ll<=mid) mn=min(mn,amn(tr[i].l,l,mid,ll,rr)); if (rr>mid) mn=min(mn,amn(tr[i].r,mid+1,r,ll,rr)); return mn;} int amx(int i,int l,int r,int ll,int rr){ if (!i) return 0; if (ll<=l&&r<=rr) return tr[i].mx; int mid=(l+r)>>1;int mx=0; if (ll<=mid) mx=max(mx,amx(tr[i].l,l,mid,ll,rr)); if (rr>mid) mx=max(mx,amx(tr[i].r,mid+1,r,ll,rr)); return mx;} int main(){ int t,i,j,a,n,k,x,y,ans,l,r,cnt;t=in(); while(t--){ n=in();k=in();ans=cz=0; for (i=1;i<=n;++i){ x=in();y=in(); ai[i]=(use){x,y,in()}; ci[++cz]=x;ci[++cz]=y; }sort(ci+1,ci+cz+1);cz=unique(ci+1,ci+cz+1)-ci-1; for (i=1;i<=n;++i){ ai[i].x=upper_bound(ci+1,ci+cz+1,ai[i].x)-ci-1; ai[i].y=upper_bound(ci+1,ci+cz+1,ai[i].y)-ci-1; }sort(ai+1,ai+n+1,cmp); memset(cc,0,sizeof(cc)); for (cnt=0,i=1;i<=n;i=j+1){ for (j=i;j<n&&ai[j+1].y==ai[i].y;++j); ans=max(ans,i-1); for (a=i;a<=j;++a) if (!cc[ai[a].c]){++cnt;cc[ai[a].c]=1;} if (cnt==k) break; }if (cnt<k) ans=n; memset(cc,0,sizeof(cc)); for (cnt=0,i=n;i;i=j-1){ for (j=i;j>1&&ai[j-1].y==ai[i].y;--j); ans=max(ans,n-i); for (a=i;a>=j;--a) if (!cc[ai[a].c]){++cnt;cc[ai[a].c]=1;} if (cnt==k) break; }if (cnt<k) ans=n; tr[0]=(tree){0,0,cz+1,0}; memset(cc,0,sizeof(cc)); memset(rt,0,sizeof(rt));tt=0; for (i=1;i<=n;i=j+1){ for (j=i;j<n&&ai[j+1].y==ai[i].y;++j); for (a=i;a<=j;++a){ l=amx(rt[ai[a].c],1,cz,1,ai[a].x); r=amn(rt[ai[a].c],1,cz,ai[a].x,cz)-1; if (l<r) ans=max(ans,cask(r)-cask(l)); }for (a=i;a<=j;++a){ ins(rt[ai[a].c],rt[ai[a].c],1,cz,ai[a].x); cins(ai[a].x); } }memset(cc,0,sizeof(cc)); memset(rt,0,sizeof(rt));tt=0; for (i=n;i;i=j-1){ for (j=i;j>1&&ai[j-1].y==ai[i].y;--j); for (a=i;a>=j;--a){ l=amx(rt[ai[a].c],1,cz,1,ai[a].x); r=amn(rt[ai[a].c],1,cz,ai[a].x,cz)-1; if (l<r) ans=max(ans,cask(r)-cask(l)); }for (a=i;a>=j;--a){ ins(rt[ai[a].c],rt[ai[a].c],1,cz,ai[a].x); cins(ai[a].x); } }sort(ai+1,ai+n+1,cmp1); ai[0]=(use){0,0,0};cc[0]=0; memset(la,0,sizeof(la)); for (i=1;i<=n;++i){ if (ai[i].x!=ai[i-1].x){ cc[ai[i].x]=cc[ai[i-1].x]; l=ai[i-1].x; }++cc[ai[i].x]; if (ai[i].x-ai[la[ai[i].c]].x>1) ans=max(ans,cc[l]-cc[ai[la[ai[i].c]].x]); la[ai[i].c]=i; }for (l=ai[n].x,i=1;i<=k;++i) ans=max(ans,cc[l]-cc[ai[la[i]].x]); printf("%d ",ans); } }
bzoj4561 圆的异或并
题目大意：给出n个没有交点的包含或者相离的圆，求被奇数个圆覆盖的面积。
思路：扫描线+fhqtreap。如果一个圆外面有奇数个圆，就要减去圆的面积，如果有偶数个就加上。把圆拆成上下端点，并按纵坐标排序。在fhqtreap中每个圆可以看作两个竖着的半圆，在上下端点的地方加入或者删除，两个半圆可以看作左右括号，统计一个圆在几个圆内就是看之前没有匹配的左括号的个数。对于不同纵坐标，相对位置关系不会变，横坐标的大小可以通过勾股定理算出来。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 200005 #define M 1000005 #define LL long long #define LD double #define eps 1e-9 using namespace std; int in(){ char ch=getchar();int x=0,f=1; while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if (ch=='-'){ch=getchar();f=-1;} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x*f;} int cmp(LD x,LD y){ if (x-y>eps) return 1; if (y-x>eps) return -1; return 0;} LL sqr(LL x){return x*x;} LD sq(LD x){return x*x;} LD ab(LD x){return (cmp(x,0.)<0 ? -x : x);} struct point{ LL x,y; bool operator<(const point&a)const{return (y==a.y ? x<a.x : y<a.y);} bool operator==(const point&a)const{return (x==a.x&&y==a.y);} }; struct circle{point c;LL r;}ci[N]; struct edge{ int k,id;point p; bool operator<(const edge&x)const{return (p==x.p ? k<x.k : p<x.p);} }bi[M]; int tt=0,rt=0,bz=0; LD dd;LL ans=0LL; struct node{ int v,sm,sz,r,id,ch[2]; void init(int vv,int kk){v=sm=vv;sz=1;id=kk;r=rand();ch[0]=ch[1]=0;} }tr[M]; void updata(int x){ tr[x].sz=1+tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz; tr[x].sm=tr[x].v+tr[tr[x].ch[0]].sm+tr[tr[x].ch[1]].sm; } int merge(int a,int b){ if (!b) return a; if (!a) return b; if (tr[a].r<tr[b].r){ tr[a].ch[1]=merge(tr[a].ch[1],b); if (a) updata(a); return a; }else{ tr[b].ch[0]=merge(a,tr[b].ch[0]); if (b) updata(b); return b; } } void split(int o,int &a,int &b,int x){ if (!o){a=b=0;return;} if (!x){a=0;b=o;return;} if (x==tr[o].sz){a=o;b=0;return;} int lz=tr[tr[o].ch[0]].sz; if (lz>=x){ split(tr[o].ch[0],a,b,x); tr[o].ch[0]=b; updata(o);b=o; }else{ split(tr[o].ch[1],a,b,x-lz-1); tr[o].ch[1]=a; updata(o);a=o; } } LD calc(int o,LD y){ LD r=(LD)ci[tr[o].id].r; LD dd=ab((LD)ci[tr[o].id].c.y-y); LD di=sqrt(sq(r)-sq(dd))*(-tr[o].v); return ci[tr[o].id].c.x+di; } int pre(int o,LD x,LD y){ if (!o) return 0; if (cmp(calc(o,y),x)<0) return tr[tr[o].ch[0]].sz+1+pre(tr[o].ch[1],x,y); else return pre(tr[o].ch[0],x,y); } void ins(int i){ int x,y,z,p,q,kk; kk=pre(rt,(LD)bi[i].p.x,(LD)bi[i].p.y); split(rt,x,y,kk); if (tr[x].sm%2) ans-=sqr(ci[bi[i].id].r); else ans+=sqr(ci[bi[i].id].r); tr[p=++tt].init(1,bi[i].id); tr[q=++tt].init(-1,bi[i].id); z=merge(p,q); rt=merge(merge(x,z),y); } void del(int i){ int x,y,p,q,kk; kk=pre(rt,(LD)bi[i].p.x,(LD)bi[i].p.y); split(rt,x,y,kk); split(y,p,q,2); rt=merge(x,q); } int main(){ int n,i;LL x,y,r; n=in(); for (i=1;i<=n;++i){ ci[i]=(circle){(point){x=(LL)in(),y=(LL)in()},r=(LL)in()}; bi[++bz]=(edge){1,i,(point){x,y-r}}; bi[++bz]=(edge){0,i,(point){x,y+r}}; }sort(bi+1,bi+bz+1); for (i=1;i<=bz;++i){ if (bi[i].k) ins(i); else del(i); }printf("%I64d ",ans); }