线段树—扫描线专题

hdu1542 Atlantis
矩形面积并
以前学线段树的时候对扫描线似懂非懂,关键是没明白为什么没有pushdown操作,现在总算弄懂了。。
因为在pushup里面当有线段覆盖时(cnt>0)直接对len域进行赋值,不依赖于儿子结点。这就相当于把这个结点当成了叶子结点(更新到底了),然后往上一路pushup,这样虽然导致该结点下面的结点信息可能有错,但是该结点以上的结点的信息保证正确。而询问是询问整段(len[1])的覆盖长度。这样每次询问时,根结点的信息是正确的就行了。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<algorithm>
using namespace std;
const double eps=1e-8;
typedef struct Seg{
    double lx,rx,h;
    int v;
}Seg;
Seg seg[210];
int n;
double tmpx[210],x[210];
bool cmp(Seg a,Seg b)
{
    return a.h<b.h;
}
bool equ(double a,double b)
{
    return fabs(a-b)<eps?1:0;
}
int bs(int l,int r,double v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(equ(x[m],v)) return m;
        if(v>x[m]) l=m+1;
        else r=m-1;
    }
    return 0;
}
#define lson id<<1
#define rson id<<1|1
const int maxn=200;
double len[maxn<<2];
int cnt[maxn<<2];
void pushup(int id,int l,int r)
{
    if(cnt[id]) len[id]=x[r+1]-x[l];
    else if(l==r) len[id]=0;
    else len[id]=len[lson]+len[rson];
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
}
int main()
{
    int i,j;
    int cases=0;
    while(~scanf("%d",&n) && n)
    {
        double x1,x2,y1,y2;
        int cc=0;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            cc++;
            tmpx[cc]=x1;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y1;seg[cc].v=1;
            cc++;
            tmpx[cc]=x2;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y2;seg[cc].v=-1;
        }
        sort(seg+1,seg+(n<<1)+1,cmp);
        sort(tmpx+1,tmpx+(n<<1)+1);
        int m=0;
        x[++m]=tmpx[1];
        for(i=2;i<=2*n;i++)
            if(!equ(tmpx[i],tmpx[i-1])) x[++m]=tmpx[i];
        memset(len,0,sizeof(len));
        memset(cnt,0,sizeof(cnt));
        double ans=0;
        for(i=1;i<=2*n-1;i++)
        {
            int l=bs(1,m,seg[i].lx);
            int r=bs(1,m,seg[i].rx)-1;
            update(1,1,m-1,l,r,seg[i].v);
            ans+=len[1]*(seg[i+1].h-seg[i].h);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",++cases,ans);
    }
    return 0;
}

hdu1828 Picture
矩形周长并

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const double eps=1e-8;
typedef struct Seg{
    int l,r,h,v;
}Seg;
Seg seg[10000+10];
int n;
bool cmp(Seg a,Seg b)
{
    return a.h<b.h;
}
#define lson id<<1
#define rson id<<1|1
const int maxn=20000;
int cnt[maxn<<2],num[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],len[maxn<<2];
void init()
{
    memset(num,0,sizeof(num));
    memset(lmax,0,sizeof(lmax));
    memset(rmax,0,sizeof(rmax));
    memset(len,0,sizeof(len));
    memset(cnt,0,sizeof(cnt));
    return;
}
void pushup(int id,int l,int r)
{
    int m=(l+r)>>1;
    if(cnt[id]) {lmax[id]=rmax[id]=len[id]=r-(l-1);num[id]=1;}
    else if(l==r) {lmax[id]=rmax[id]=len[id]=0;num[id]=0;}
    else
    {
        lmax[id]=(lmax[lson]==(m-(l-1))?lmax[lson]+lmax[rson]:lmax[lson]);
        rmax[id]=(rmax[rson]==(r-m)?rmax[rson]+rmax[lson]:rmax[rson]);
        len[id]=len[lson]+len[rson];
        num[id]=num[lson]+num[rson]+((rmax[lson] && lmax[rson])?-1:0);
    }
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
    return;
}
int main()
{
    int i,j;
    int last;
    while(~scanf("%d",&n))
    {
        int x1,y1,x2,y2;
        int c=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1+=10000;x2+=10000;
            c++;
            seg1.l=x1;seg1.r=x2;seg1.h=y1;seg1.v=1;
            c++;
            seg1.l=x1;seg1.r=x2;seg1.h=y2;seg1.v=-1;
        }
        sort(seg+1,seg+1+(n<<1),cmp);
        last=0;
        int ans=0;
        init();
        for(i=1;i<=(n<<1);i++)
        {
            update(1,1,20000,seg[i].l+1,seg[i].r,seg[i].v);
            ans+=abs(len[1]-last);
            ans+=num[1]*2*(seg[i+1].h-seg[i].h);
            last=len[1];
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu1255 覆盖的面积
这题扫描的时候需要维护区间被覆盖两次及以上的长度。
线段树维护len(覆盖一次及以上的长度)、nlen(覆盖两次及以上的长度)、cnt(覆盖线段条数)
理解两个pushup函数需要清楚几点:
1.由于没有pushdown操作,所以某个结点的cnt和其子结点的cnt是无关的。也就是说,父节点cnt=1,子结点cnt=1,那么显然有两条不同的线段覆盖在子结点上。
2.每个结点的len、nlen维护的是该结点及以下结点的信息,有点dp的感觉,这样就保证了最顶端结点(根结点)信息的正确。
3.由2可以知道,上层结点信息的更新不会改变下层结点的信息,反之则会。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const int maxn=2010;
#define zero(x) (fabs(x)<eps?1:0)
typedef struct Seq{
    double lx,rx,h;
    int v;
}Seg;
Seg seg[maxn];
int n;
double tmpx[maxn],x[maxn];
double len[maxn<<2],nlen[maxn<<2];
int cnt[maxn<<2];
bool cmp(Seg a,Seg b) {return a.h<b.h;}
int bs(int l,int r,double v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(zero(x[m]-v)) return m;
        if(v>x[m]) l=m+1;
        else r=m-1;
    }
    return 0;
}
#define lson id<<1
#define rson id<<1|1
void init()
{
    memset(len,0,sizeof(len));
    memset(nlen,0,sizeof(nlen));
    memset(cnt,0,sizeof(cnt));
    return;
}
void pushup1(int id,int l,int r)
{
    if(cnt[id]) len[id]=x[r+1]-x[l];
    else if(l==r) len[id]=0;
    else len[id]=len[lson]+len[rson];
    return;
}
void pushup2(int id,int l,int r)
{
    if(cnt[id]>1) nlen[id]=x[r+1]-x[l];
    else if(cnt[id]==1)
    {
        if(l==r) nlen[id]=0;
        else nlen[id]=len[lson]+len[rson];
    }
    else
    {
        if(l==r) nlen[id]=0;
        else nlen[id]=nlen[lson]+nlen[rson];
    }
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup1(id,l,r);
        pushup2(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup1(id,l,r);
    pushup2(id,l,r);
    return;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        double x1,y1,x2,y2;
        int cc=0;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            cc++;
            tmpx[cc]=x1;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y1;seg[cc].v=1;
            cc++;
            tmpx[cc]=x2;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y2;seg[cc].v=-1;
        }
        sort(seg+1,seg+1+(n<<1),cmp);
        sort(tmpx+1,tmpx+1+(n<<1));
        int m=0;tmpx[0]=-1;
        for(i=1;i<=(n<<1);i++) if(!zero(tmpx[i]-tmpx[i-1])) x[++m]=tmpx[i];
        init();
        double ans=0;
        for(i=1;i<=(n<<1)-1;i++)
        {
            int l=bs(1,m,seg[i].lx);
            int r=bs(1,m,seg[i].rx)-1;
            update(1,1,m-1,l,r,seg[i].v);
            ans+=nlen[1]*(seg[i+1].h-seg[i].h);
        }
        printf("%.2f\n",ans);
    }
    return 0;
}

hdu3265 Posters
矩形面积并,但是每个矩形中间挖去一个小矩形。所以要把一个矩形分成四个矩形做

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=50000;
int len[maxn<<2],cnt[maxn<<2];
typedef struct Seg{
    int l,r,h,v;
}Seg;
int n;
Seg seg[(maxn<<3)+10];
void init()
{
    memset(cnt,0,sizeof(cnt));
    memset(len,0,sizeof(len));
    return;
}
bool cmp(Seg a,Seg b)
{
    //if(a.h==b.h) return a.v>b.v;
    return a.h<b.h;
}
int x1,x2,x3,x4,y1,y2,y3,y4;
int cc;
void cal()
{
    if(y1!=y3 && x1!=x2)
    {
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y1;seg[cc].v=1;
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y3;seg[cc].v=-1;
    }
    if(y2!=y4 && x1!=x2)
    {
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y4;seg[cc].v=1;
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y2;seg[cc].v=-1;
    }
    if(y3!=y4 && x1!=x3)
    {
        cc++;
        seg[cc].l=x1;seg[cc].r=x3;seg[cc].h=y3;seg[cc].v=1;
        cc++;
        seg[cc].l=x1;seg[cc].r=x3;seg[cc].h=y4;seg[cc].v=-1;
    }
    if(y3!=y4 && x4!=x2)
    {
        cc++;
        seg[cc].l=x4;seg[cc].r=x2;seg[cc].h=y3;seg[cc].v=1;
        cc++;
        seg[cc].l=x4;seg[cc].r=x2;seg[cc].h=y4;seg[cc].v=-1;
    }
    return;
}
void pushup(int id,int l,int r)
{
    if(cnt[id]) len[id]=r-l+1;
    else if(l==r) len[id]=0;
    else len[id]=len[lson]+len[rson];
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n) && n)
    {
        cc=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
            cal();
        }
        sort(seg+1,seg+1+cc,cmp);
        init();
        long long ans=0;
        for(i=1;i<=cc-1;i++)
        {
            update(1,1,maxn,seg[i].l+1,seg[i].r,seg[i].v);
            ans+=(long long)len[1]*(long long)(seg[i+1].h-seg[i].h);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

hdu3642 Get The Treasury
矩形体积并,这题吊吊吊,写了好久,细节比较烦,思路其实和矩形面积并一样的,z从小往大扫描,每扫到一个面,就往seg中加入或删去两条线段(相当于加入或减去一个矩形,扫描到长方体的下面则加两条线段,扫描到长方体的上面则减两条线段),然后求矩形面积并。每次用这个并面积(起码三个面并)乘上z轴差,就是增加的体积。
x坐标需要离散话,否则MLE。我的代码里面用了一点小暴力:seg数组元素用一个use域表示这条线段是否存在,按y轴从小到大扫描时,每次都要顺序查找吓一条use=1的线段。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
typedef long long ll;
const int maxn=2000;
typedef struct Seg{
    int l,r,h,v;
    int num1,num2;
    int use;
}Seg;
typedef struct Cube{
    int down,up;
    int z;
    int v;
}Cube;
Cube cube[2010];
Seg seg[2010];
int n,m,x1,x2,y1,y2,z1,z2,cc,cn;
int x[2010],tmpx[2010];
bool cmp(Seg a,Seg b)
{
    return a.h<b.h;
}
bool cmp2(Cube a,Cube b)
{
    return a.z<b.z;
}
int alen[maxn<<2],blen[maxn<<2],clen[maxn<<2],cnt[maxn<<2];
void init()
{
    memset(alen,0,sizeof(alen));
    memset(blen,0,sizeof(blen));
    memset(clen,0,sizeof(clen));
    memset(cnt,0,sizeof(cnt));
    return;
}
void pushup1(int id,int l,int r)
{
    if(cnt[id]) alen[id]=x[r+1]-x[l];
    else if(l==r) alen[id]=0;
    else alen[id]=alen[lson]+alen[rson];
    return;
}
void pushup2(int id,int l,int r)
{
    if(cnt[id]>1) blen[id]=x[r+1]-x[l];
    else if(cnt[id]==1)
    {
        if(l==r) blen[id]=0;
        else blen[id]=alen[lson]+alen[rson];
    }
    else
    {
        if(l==r) blen[id]=0;
        else blen[id]=blen[lson]+blen[rson];
    }
    return;
}
void pushup3(int id,int l,int r)
{
    if(cnt[id]>2) clen[id]=x[r+1]-x[l];
    else if(cnt[id]==2)
    {
        if(l==r) clen[id]=0;
        else clen[id]=alen[lson]+alen[rson];
    }
    else if(cnt[id]==1)
    {
        if(l==r) clen[id]=0;
        else clen[id]=blen[lson]+blen[rson];
    }
    else
    {
        if(l==r) clen[id]=0;
        else clen[id]=clen[lson]+clen[rson];
    }
    return;
}
void pushup(int id,int l,int r)
{
    pushup1(id,l,r);
    pushup2(id,l,r);
    pushup3(id,l,r);
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
    return;
}
int bs(int l,int r,int v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(x[m]==v) return m;
        if(v<x[m]) r=m-1;
        else l=m+1;
    }
    return 0;
}
ll cal()
{
    int i,j;
    init();
    ll ans=0;
    for(i=1;i<=cc;i++)
    {
        if(!seg[i].use) continue;
        int l=bs(1,m,seg[i].l);
        int r=bs(1,m,seg[i].r)-1;
        update(1,1,m-1,l,r,seg[i].v);
        for(j=i+1;j<=cc+1;j++) if(seg[j].use) break;
        ans+=(ll)clen[1]*(ll)(seg[j].h-seg[i].h);
    }
    return ans;
}
int main()
{
    int i,j;
    int t,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        cc=cn=m=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);x1+=1000000;x2+=1000000;
            tmpx[++m]=x1;tmpx[++m]=x2;
            cube[++cn].z=z1;cube[cn].v=1;
            cube[++cn].z=z2;cube[cn].v=0;
            cc++;
            seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y1;seg[cc].v=1;seg[cc].use=0;
            seg[cc].num1=cn-1;seg[cc].num2=cn;
            cc++;
            seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y2;seg[cc].v=-1;seg[cc].use=0;
            seg[cc].num1=cn-1;seg[cc].num2=cn;
        }
        sort(tmpx+1,tmpx+1+m);
        int tmp=0;
        tmpx[0]=-1;
        for(i=1;i<=m;i++)
            if(tmpx[i]!=tmpx[i-1]) x[++tmp]=tmpx[i];
        m=tmp;
        sort(seg+1,seg+1+cc,cmp);
        seg[cc+1].h=0;seg[cc+1].use=1;
        for(i=1;i<=cc;i++)
        {
            int num1=seg[i].num1,num2=seg[i].num2;
            int v=seg[i].v;
            if(v<0) cube[num1].down=cube[num2].down=i;
            else cube[num1].up=cube[num2].up=i;
        }
        sort(cube+1,cube+1+cn,cmp2);
        ll ans=0;
        for(i=1;i<=cn-1;i++)
        {
            int down=cube[i].down,up=cube[i].up,use=cube[i].v;
            seg[down].use=use;seg[up].use=use;
           // printf("area:%I64d   zh:%d\n",cal(),cube[i+1].z-cube[i].z);
            ans+=cal()*(ll)(cube[i+1].z-cube[i].z);
        }
        printf("Case %d: %I64d\n",++cases,ans);
    }
    return 0;
}

poj2482 Stars in Your Window
这题很有意思,给出一些点,每个点都有一个权值。给出一个长宽固定的矩形A,矩形可以平移,问最多可以圈住多少点权。(边界上的点不算)
这个问题需要巧妙的转化:对于每个点,发散出一个矩形范围,当A的中心在该范围内时,可以圈住该点。那么显然这个矩形范围和矩形A长的一模一样。问题就转化为平面上最多有多少个矩形重叠。这样就可以用成段更新的线段树+扫描线解决。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
#define zero(x) (fabs(x)<eps?1:0)
using namespace std;
const int maxn=2e4;
const double eps=1e-8;
double tmpx[maxn+10],x[maxn+10];
int cnt[maxn<<2],add[maxn<<2];
inline int max(int a,int b){return a>b?a:b;}
typedef struct Seg{
    double l,r,h;
    int v;
}Seg;
int n,m,w,h;
Seg seg[(maxn<<1)+10];
bool cmp(Seg a,Seg b)
{
    if(zero(a.h-b.h)) return a.v<b.v;
    return a.h<b.h;
}
void init()
{
    memset(cnt,0,(n<<3)*sizeof(cnt[0]));
    memset(add,0,(n<<3)*sizeof(add[0]));
    return;
}
void pushup(int id)
{
    cnt[id]=max(cnt[lson],cnt[rson]);
    return;
}
void pushdown(int id)
{
    if(!add[id]) return;
    cnt[lson]+=add[id];add[lson]+=add[id];
    cnt[rson]+=add[id];add[rson]+=add[id];
    add[id]=0;
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        add[id]+=v;
        return;
    }
    pushdown(id);
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id);
    return;
}
int bs(int l,int r,double v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(zero(v-x[m])) return m;
        if(v<x[m]) r=m-1;
        else l=m+1;
    }
    return 0;
}
int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&w,&h))
    {
        int cc=0,cn=0;
        int a,b,c;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            tmpx[++cn]=a-w/2.0;tmpx[++cn]=a+w/2.0;
            cc++;
            seg[cc].l=a-w/2.0;seg[cc].r=a+w/2.0;seg[cc].h=b-h/2.0;seg[cc].v=c;
            cc++;
            seg[cc].l=a-w/2.0;seg[cc].r=a+w/2.0;seg[cc].h=b+h/2.0;seg[cc].v=-c;
        }
        sort(seg+1,seg+1+cc,cmp);
        sort(tmpx+1,tmpx+1+cn);
        tmpx[0]=-1;
        m=0;
        for(i=1;i<=cn;i++) if(!zero(tmpx[i]-tmpx[i-1])) x[++m]=tmpx[i];
        init();
        int ans=0;
        for(i=1;i<=cc;i++)
        {
            int l=bs(1,m,seg[i].l);
            int r=bs(1,m,seg[i].r)-1;
            update(1,1,m-1,l,r,seg[i].v);
            if(cnt[1]>ans) ans=cnt[1];
        }
        printf("%d\n",ans);
    }
    return 0;
}

莫队算法专题

把几道莫队算法的题集中写一下
HYSBZ 2038 小Z的袜子
经典的莫队算法

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=50000+10;
int n,m;
ll a[maxn],cnt[maxn];
typedef struct Query{
    ll l,r,num,ans1,ans2;
}Query;
Query q[maxn];
ll ans[maxn][2];
ll ret,len;
int gcd(ll a,ll b)
{
    if(a<b) {a^=b;b^=a;a^=b;}
    return b==0?a:gcd(b,a%b);
}
bool cmp(Query a,Query b)
{
    if(a.l/len==b.l/len) return a.r<b.r;
    return a.l<b.l;
}
void add(int x)
{
    ret-=cnt[a[x]]*(cnt[a[x]]-1);
    cnt[a[x]]++;
    ret+=cnt[a[x]]*(cnt[a[x]]-1);
    return;
}
void del(int x)
{
    ret-=cnt[a[x]]*(cnt[a[x]]-1);
    cnt[a[x]]--;
    ret+=cnt[a[x]]*(cnt[a[x]]-1);
    return;
}
void cal(ll l1,ll r1,ll l2,ll r2)
{
    while(r1<r2) {r1++;add(r1);}
    while(r1>r2) {del(r1);r1--;}
    while(l1<l2) {del(l1);l1++;}
    while(l1>l2) {l1--;add(l1);}
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].num=i;
        }
        len=(ll)sqrt(n*1.0);
        sort(q+1,q+1+m,cmp);

        ret=0;memset(cnt,0,sizeof(cnt));
        q[0].l=1;q[0].r=0;
        for(i=1;i<=m;i++)
        {
            ll l=q[i].l,r=q[i].r;
            cal(q[i-1].l,q[i-1].r,l,r);
            ll tmp=gcd(ret,(r-l+1)*(r-l));
            q[i].ans1=ret/tmp;q[i].ans2=(r-l+1)*(r-l)/tmp;
        }
        for(i=1;i<=m;i++)
        {
            int id=q[i].num;
            ans[id][0]=q[i].ans1;
            ans[id][1]=(q[i].ans1==0?1:q[i].ans2);
        }
        for(i=1;i<=m;i++) printf("%lld/%lld\n",ans[i][0],ans[i][1]);
    }
    return 0;
}

NBUT 1457 Sona
先把数据映射为1~n。
转移必须为O(1),总复杂度O(n^1.5lgn)会超时。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=100000+10;
int n,m;
int a[maxn];
map<int,int> num;
typedef struct Query{
    int l,r,id;
}Query;
Query q[maxn];
int len;
ll ret;
ll cnt[maxn];
ll ans[maxn];
bool cmp(Query a,Query b)
{
    if(a.l/len==b.l/len) return a.r<b.r;
    return a.l<b.l;
}
void add(int x)
{
    ll &y=cnt[a[x]];
    ret-=y*y*y;
    y++;
    ret+=y*y*y;
    return;
}
void del(int x)
{
    ll &y=cnt[a[x]];
    ret-=y*y*y;
    y--;
    ret+=y*y*y;
    return;
}
void cal(int l1,int r1,int l2,int r2)
{
    while(r1<r2) {r1++;add(r1);}
    while(r1>r2) {del(r1);r1--;}
    while(l1<l2) {del(l1);l1++;}
    while(l1>l2) {l1--;add(l1);}
    return;
}
void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++) scan(a[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scan(q[i].l);scan(q[i].r);
            q[i].id=i;
        }
        len=(int)sqrt(n*1.0);
        sort(q+1,q+1+m,cmp);
        if(!num.empty()) num.clear();
        int iq=0;
        for(i=1;i<=n;i++)
        {
            if(num.find(a[i])==num.end()) num[a[i]]=++iq;
        }
        for(i=1;i<=n;i++) a[i]=num[a[i]];
        ret=0;q[0].l=1;q[0].r=0;
        memset(cnt,0,sizeof(cnt));
        for(i=1;i<=m;i++)
        {
            cal(q[i-1].l,q[i-1].r,q[i].l,q[i].r);
            ans[q[i].id]=ret;
        }
        for(i=1;i<=m;i++) printf("%I64d\n",ans[i]);
    }
    return 0;
}

hdoj搜索题集

n久没刷题了,感觉水平退化太多了。。今天开始刷题。
把hdoj以前没做的搜索题做一下
hdu1072 简单题
我的思路:出发点和可重置时间的点没有必要访问两次,其他点可以重复访问。这样不会导致bfs一直进行下去。
其他思路:对于这种点可以重复访问的题,bfs入队时不仅要考虑坐标,还要考虑剩余时间,如果同一个点第二次入队时剩余时间比第一次大于或等于,那么不需要入队,没有意义。

#include<stdio.h>
#include<string.h>
const int maxq=1000000;
int n,m;
int map[9][9];
int vis[9][9];
typedef struct Node{
    int x,y,t,step;
}Node;
Node q[maxq];
int iq;
int dirx[]={0,1,-1,0,0};
int diry[]={0,0,0,1,-1};
int sx,sy,tx,ty,x,y,tt,step;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=sx;q[iq].y=sy;q[iq].t=6;q[iq].step=0;
    iq++;vis[sx][sy]=1;
    for(i=0;i<=iq-1;i++)
    {
        x=q[i].x;y=q[i].y;tt=q[i].t;step=q[i].step;
        if(tt==1) continue;
        for(j=1;j<=4;j++)
        {
            int u=x+dirx[j],v=y+diry[j];
            if(map[u][v]==3) return step+1;
            if(!judge(u,v) || vis[u][v] || map[u][v]==0) continue;
            if(map[u][v]==4) vis[u][v]=1;
            q[iq].x=u;q[iq].y=v;q[iq].t=tt-1;q[iq].step=step+1;
            if(map[u][v]==4) q[iq].t=6;
            iq++;
        }
    }
    return -1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                if(map[i][j]==2) sx=i,sy=j;
                if(map[i][j]==3) tx=i,ty=j;
            }
        printf("%d\n",bfs());
    }
    return 0;
}

hdu1026 简单题
如果答案是1 second,仍然输出1 seconds哦

#include<stdio.h>
#include<string.h>
const int maxq=100000+10;
int n,m;
char map[110][110];
bool vis[110][110];
typedef struct Node{
    int x,y,t,tt;
    int pre;
}Node;
Node q[maxq];
int iq;
int a[]={0,1,-1,0,0};
int b[]={0,0,0,1,-1};
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=1;q[iq].y=1;q[iq].t=0;q[iq].pre=-1;
    iq++;
    vis[1][1]=1;
    for(i=0;i<=iq-1;i++)
    {
        int x=q[i].x,y=q[i].y,t=q[i].t,tt=q[i].tt;
        if(x==n && y==m)
        {
            if('1'<=map[n][m] && map[n][m]<='9')
            {
                if(!tt) return i;
            }
            else return i;
        }
        if('1'<=map[x][y] && map[x][y]<='9' && tt)
        {
            q[iq].x=x;q[iq].y=y;q[iq].t=t+1;q[iq].tt=tt-1;
            q[iq++].pre=i;
            continue;
        }
        for(j=1;j<=4;j++)
        {
            int u=x+a[j],v=y+b[j];
            if(!judge(u,v) || vis[u][v] || map[u][v]=='X') continue;
            q[iq].x=u;q[iq].y=v;q[iq].t=t+1;q[iq].tt=map[u][v]-'0';
            q[iq++].pre=i;
            vis[u][v]=1;
        }
    }
    return -1;
}
void dfs(int cur)
{
    int x=q[cur].x,y=q[cur].y,t=q[cur].t,pre=q[cur].pre;
    int px=q[pre].x,py=q[pre].y;
    if(px==1 && py==1)
    {
        printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
        return;
    }
    dfs(pre);
    if(px==x && py==y) printf("%ds:FIGHT AT (%d,%d)\n",t,x-1,y-1);
    else printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                scanf("%c",&map[i][j]);
            getchar();
        }
        int ans=bfs();
        if(ans==-1) {printf("God please help our poor hero.\nFINISH\n");continue;}
        printf("It takes %d seconds to reach the target position, let me show you the way.\n",q[ans].t);
        dfs(ans);
        printf("FINISH\n");

    }

    return 0;
}