数据结构 – 第 10 页

ZOJ 2112 线段树+平衡树

题意：

N<=50000 M<=10000

给定一个数组A[1]~A[N]，有M个操作

每个操作可以如下

Q i j t 输出 A[I]~A[J]之间第t小的数

C i t 将A[I]赋值为t

解题分析：

线段树套一个平衡树，然后二分答案。

利用线段树和平衡树来求区间内<=这个数的数的个数。

复杂度O(M(lgN)^3)

code：

#include #include #define L(x) ((x)*2)
#define R(x) ((x)*2+1)
#define N 1000001
#define INF 0x7FFFFFFF/2-10
#define min(x,y) (x)<(y)?(x):(y)

struct SbtTreeType{int l,r,s,w;}tr[N];
struct InterZoneType{int l,r,root;}T[N];
int a[N],n,m,tot;

void Left(int &p){
    int t=tr[p].r;
    tr[p].r=tr[t].l;
    tr[t].l=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void Right(int &p){
    int t=tr[p].l;
    tr[p].l=tr[t].r;
    tr[t].r=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void repair(int &p){
    bool flag=false;
    if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
        Left(tr[p].l);
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
        Left(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
        Right(tr[p].r);
        Left(p);
        flag=true;
    }
    if (flag){
        repair(tr[p].l);
        repair(tr[p].r);
        repair(p);
    }
}

void ins(int &p,int w){
    if (p==0){
        tr[++tot].l=0;
        tr[tot].r=0;
        tr[tot].s=1;
        tr[tot].w=w;
        p=tot;
        return;
    }
    if (w<=tr[p].w) ins(tr[p].l,w);
               else ins(tr[p].r,w);
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    repair(p);
}

int del(int &p,int w){
    tr[p].s–;
    if (tr[p].w==w || tr[p].l==0 && w<=tr[p].w || tr[p].r==0 && w>tr[p].w){
        int delnum=tr[p].w;
        if (tr[p].l==0 || tr[p].r==0) p=tr[p].l+tr[p].r;
        else tr[p].w=del(tr[p].l,0x7FFFFFFF);
        return delnum;
    }
    if (w<=tr[p].w) return del(tr[p].l,w);
               else return del(tr[p].r,w);
}

void Build(int p,int l,int r){
    T[p].l=l; T[p].r=r; T[p].root=0;
    int i;
    for (i=l;i<=r;i++) ins(T[p].root,a[i]);
    if (l        int mid=(l+r)/2;
        Build(L(p),l,mid);
        Build(R(p),mid+1,r);
    }
}

void Change(int p,int pos,int pre,int key){
    if (pos    del(T[p].root,pre);
    ins(T[p].root,key);
    if (T[p].l        Change(L(p),pos,pre,key);
        Change(R(p),pos,pre,key);
    }
}

int rank(int p,int w){
if (p==0) return 0;
if (w return (tr[tr[p].l].s+1+rank(tr[p].r,w));
}

int Getnum(int p,int l,int r,int x){
    if (r    if (l<=T[p].l && T[p].r<=r) return rank(T[p].root,x);
    int tx=Getnum(L(p),l,r,x),ty=Getnum(R(p),l,r,x);
    return (tx+ty);
}

void work(){
    int i;
    tot=0;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    Build(1,1,n);
    char ch;
    int il,ir,dj,x,y,l,r,mid;
    for (i=1;i<=m;i++){
        scanf("%c",&ch);
        while (ch==10 || ch==13) scanf("%c",&ch);
        if (ch!=’C’){
            scanf("%d%d%d",&il,&ir,&dj);
            l=-INF;
            r=INF;
            while (l                mid=(l+r)/2;
                if (Getnum(1,il,ir,mid)                                       else r=mid;
            }
            printf("%dn",l);
        }
        else {
            scanf("%d%d",&x,&y);
            Change(1,x,a[x],y);
            a[x]=y;
        }
    }
}

int main(){
    int TC;
    scanf("%d",&TC);
    int i;
    for (i=1;i<=TC;i++)
      work();
    return 0;
}

POJ 2985 并差集+SBT

题目大意：

有N只猫，M个操作。

操作种类如下：

0：把两只猫所在的组合并

1：数量第K大的组的数量是多少。

题目分析：

很容易想到用并差集合并组。但是至于那个第K大的组怎么求，可以用树状数组或者平衡树或者线段树。反正选一个用就好了。

插曲：

调了N久，发现delete操作之前没有真正理解。写错了。。。现在总算懂了。

实际上delete是会破坏SBT性质的。但是在插入的时候会修复。所以树的总高度将会是O(lgn)，其中n为插入操作执行的次数。

code:

#include #include #define N 200001
using namespace std;
struct treetype{int w,l,r,s;} tr[N*4];
int n,operate,f[N],tot,root,num[N];

void Left(int &p){
    int t=tr[p].r;
    tr[p].r=tr[t].l;
    tr[t].l=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void Right(int &p){
    int t=tr[p].l;
    tr[p].l=tr[t].r;
    tr[t].r=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

int gf(int p){
    if (f[p]==p) return p;
    f[p]=gf(f[p]);
    return f[p];
}

int Find(int p,int k){
    if (tr[tr[p].r].s+1==k) return tr[p].w;
    if (tr[tr[p].r].s>=k) return Find(tr[p].r,k);
    return Find(tr[p].l,k-tr[tr[p].r].s-1);
}

void init(){
    tot=0; root=0;
    for (int i=1;i<=n;i++){
      f[i]=i;
      num[i]=1;
      ins(root,1);
    }
}

void work(){
    int op,x,y;
    for (int i=1;i<=operate;i++){
        scanf("%d",&op);
        if (op==0){
            scanf("%d%d",&x,&y);
            if (gf(x)==gf(y)) continue;
            if (num[f[x]]>num[f[y]]) swap(x,y);
            del(root,num[f[x]]);
            del(root,num[f[y]]);
            num[f[y]]+=num[f[x]];
            num[f[x]]=0;
            ins(root,num[f[y]]);
            f[f[x]]=f[y];
        }
        else{
            scanf("%d",&x);
            printf("%dn",Find(root,x));
        }
    }
}

int main(){
    scanf("%d%d",&n,&operate);
    init();
    work();
}

POJ 2482 扫描线+离散化+线段树 (内容最浪漫的题目)

http://162.105.81.212/JudgeOnline/problem?id=2482

题目大意：

给定一个W*H的矩形，再给出一些在平面直角坐标系里的星星，每个星星有一个亮度，求用这个矩形去框住一些星星，使得框内的星星亮度之和最大。

HINT:

压在矩形的右边框或下边框的星星不算被框住。

其实一开始把w和h分别减1，然后按矩形处理就可以了。

另外要使用INT64

解题分析：

这个题目可以先把y坐标离散化。然后在Y轴建立线段树，再扫描X轴，动态维护一个关于x坐标的极大范围。然后用线段树维护最大值即可。注意，在Y轴上的插入的线段表示的是把这个范围内的点作为最高点，能够覆盖到星星i。

插曲：

这是GDOI之前老姜要求做的一题。当时看到晕掉了没做，在学校调了一周没调出来，老是WA。最后理清思路，在家重打了一遍，一次编译成功，一次AC。

code：

#include #include #include #include #define L(x) (x)<<1
#define R(x) ((x)<<1)|1
#define MAXN 111111
using namespace std;
struct startype{__int64 x,y,w;}a[MAXN];
struct treetype{__int64 l,r,max,sum;}tr[MAXN*20];
__int64 n,xlen,ylen,yl[MAXN],m,tl[MAXN],toy[MAXN];

void DelSame(){
    m=0;
    for (__int64 i=1;i<=n;i++)
      if (m==0 || tl[m]!=yl[i])
        tl[++m]=yl[i];
    for (__int64 i=1;i<=n;i++) yl[i]=0;
    for (__int64 i=1;i<=m;i++) yl[i]=tl[i];
}

__int64 Find(__int64 k){
    __int64 l=1,r=m,mid;
    while (l        mid=l+r>>1;
        if (yl[mid]                  else r=mid;
    }
    return l;
}

void LiSan(){
    for (__int64 i=1;i<=n;i++)
      yl[i]=a[i].y;
    sort(&yl[1],&yl[n+1]);
    DelSame();
    for (__int64 i=1;i<=n;i++)
      a[i].y=Find(a[i].y);
}

void Build(__int64 p,__int64 l,__int64 r){
    tr[p].l=l; tr[p].r=r; tr[p].max=0; tr[p].sum=0;
    if (l        __int64 mid=l+r>>1;
        Build(L(p),l,mid);
        Build(R(p),mid+1,r);
    }
}

bool cmp(startype t1,startype t2){
if (t1.x return false;
}

void Toy(){
    __int64 i,j=0;
    for (i=1;i<=m;i++){
        while (j        toy[i]=j;
    }
}

void ins(__int64 p,__int64 l,__int64 r,__int64 w){
    if (r    if (l<=tr[p].l && tr[p].r<=r){
        tr[p].sum+=w;
        tr[p].max+=w;
        return;
    }
    if (tr[p].sum!=0){
        ins(L(p),0,m,tr[p].sum);
        ins(R(p),0,m,tr[p].sum);
        tr[p].sum=0;
    }
    ins(L(p),l,r,w);
    ins(R(p),l,r,w);
    tr[p].max=max(tr[L(p)].max,tr[R(p)].max);
}

void Work(){
    sort(&a[1],&a[n+1],cmp);
    __int64 i,j=0,ans=0;
    for (i=1;i<=n;i++){
        while (j            j++;
            ins(1,a[j].y,toy[a[j].y],a[j].w);
        }
        ans=max(ans,tr[1].max);
        ins(1,a[i].y,toy[a[i].y],-a[i].w);
    }
    cout << ans << endl;
}

int main(){
    while (cin >> n >> xlen >> ylen){
        xlen–; ylen–;
        for (__int64 i=1;i<=n;i++)
          scanf("%I64d %I64d %I64d",&a[i].x,&a[i].y,&a[i].w);
        LiSan();
        Build(1,1,m);
        Toy();
        Work();
    }
    return 0;
}

POJ 2823 单调队列

题意：

有N个数，每次从左至右选M个数，即[1..M]，[2..M+1]，…，[M-N+1..N]，选取每个区间的最大值和最小值。

解题分析：

明显的单调队列解决，复杂度O(N)

但是却跑了6000+MS。不知道那些500MS的怎么跑出来的。

code：

#include #define N 1000001
using namespace std;

int n,m,a[N],qf[N],qn[N];

void init(){
     scanf("%d%d",&n,&m);
     for (int i=1;i<=n;i++)
       scanf("%d",&a[i]);
}

void work1(){
     int head=1,tail=0;
     for (int i=1;i         while (head<=tail && qf[tail]>=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
     }
     for (int i=m;i<=n;i++){
         while (head<=tail && qf[tail]>=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
         while (qn[head]         printf("%d",qf[head]);
         if (i!=n) cout << " ";
     }
     cout << endl;
}

void work2(){
     int head=1,tail=0;
     for (int i=1;i         while (head<=tail && qf[tail]<=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
     }
     for (int i=m;i<=n;i++){
         while (head<=tail && qf[tail]<=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
         while (qn[head]         printf("%d",qf[head]);
         if (i!=n) cout << " ";
     }
     cout << endl;

}

int main(){
    init();
    work1();
    work2();
    return 0;
}

HDOJ 1823 二维线段树

http://acm.hdu.edu.cn/showproblem.php?pid=1823 题目是中文的。

题意：

给定一些点对(x,y)，和这些点对的权值。求满足(x1<=x<=x2 && y1<=y<=y2)的点里权值最大的一个。

由于小数点只有一个，所以把他*10就可以当整数处理。

解题思路：

标准的二维线段树的应用。建立二维线段树动态维护即可。

收获：

学会了二维线段树，但TLE了好几次。

究其原因，是我以为在#define里定义的max函数和真正的函数是一样的，但实际上是替换而已。

直接调用max(solve(xxxx),solve(xxxx))这样C++会计算两次。导致超时。以后max里不要调用函数。

要调用先用变量存起来。

code：

#include #define L(x) (x)<<1
#define R(x) ((x)<<1)|1
#define round(x) (int)((x)+0.5)
#define max(x,y) (x)>(y)?(x):(y)
struct atype{int l,r;} a[300];
struct btype{int l,r,max;} b[300][3000];

int m;

void swap(double &x,double &y){
double t;
t=x; x=y; y=t;
}

void buildy(int p,int x,int l,int r){
     b[x][p].l=l; b[x][p].r=r; b[x][p].max=-1;
     if (l       int mid=l+r>>1;
       buildy(L(p),x,l,mid);
       buildy(R(p),x,mid+1,r);
     }
}

void buildx(int p,int l,int r){
     a[p].l=l; a[p].r=r;
     buildy(1,p,0,1000);
     if (l       int mid=l+r>>1;
       buildx(L(p),l,mid);
       buildx(R(p),mid+1,r);
     }
}

void inserty(int p,int x,int y,int data){
     if (b[x][p].l==b[x][p].r){
       b[x][p].max=max(b[x][p].max,data);
       return;
     }
     if (b[x][p].max==-1){
       b[x][L(p)].max=-1;
       b[x][R(p)].max=-1;
     }
     int mid=b[x][p].l+b[x][p].r>>1;
     if (y<=mid) inserty(L(p),x,y,data);
            else inserty(R(p),x,y,data);
     b[x][p].max=max(b[x][p].max,data);
}

void insertx(int p,int x,int y,int data){
     inserty(1,p,y,data);
     if (a[p].l==a[p].r) return;
     int mid=a[p].l+a[p].r>>1;
     if (x<=mid) insertx(L(p),x,y,data);
            else insertx(R(p),x,y,data);
}

int solvey(int p,int x,int y1,int y2){
    if (y2    if (b[x][p].l>=y1 && y2>=b[x][p].r) return b[x][p].max;
    int t1=solvey(L(p),x,y1,y2),t2=solvey(R(p),x,y1,y2);
    return max(t1,t2);
}

int solvex(int p,int x1,int x2,int y1,int y2){
    if (x1>a[p].r || x2    if (a[p].l>=x1 && x2>=a[p].r) return solvey(1,p,y1,y2);
    int t1=solvex(L(p),x1,x2,y1,y2),t2=solvex(R(p),x1,x2,y1,y2);
    return max(t1,t2);
}

void work(){
     for (int i=1;i<=m;i++){
         char operate;
         scanf("%c",&operate);
         if (operate==’I’){
           int height;
           double A,L;
           scanf("%d %lf %lfn",&height,&A,&L);
           insertx(1,height,round(A*10),round(L*10));
         }
         else{
           double h1,h2,a1,a2;
           scanf("%lf %lf %lf %lfn",&h1,&h2,&a1,&a2);
           if (h1>h2) swap(h1,h2);
           if (a1>a2) swap(a1,a2);
           int ans=solvex(1,round(h1),round(h2),round(a1*10),round(a2*10));
           if (ans==-1) printf("-1n");
                   else printf("%d.%dn",ans/10,ans%10);
         }
     }
}

void init(){
for (int i=0;i<300;i++) b[i][1].max=-1;
}

int main(){
    buildx(1,100,200);
    for (;;){
        scanf("%dn",&m);
        if (m==0) break;
        init();
        work();
    }
    return 0;
}