edward_mj

SPOJ 726 大根堆+小根堆 || 平衡树

题目：

https://www.spoj.pl/problems/PRO/

题意描述：

总共N天，每天取已加入的数的最大值和最小值相减并累加到ans，并删掉这两个数。

数据保证每天至少有两个数可以删。

解题分析：

这题可以建两个堆，然后按题意模拟，但是用平衡树更方便。

我用的是SBT。比堆更简短。

插曲：

WA到2B去了。。。原来是要用INT64

code:

#include #include #include #define N 1000000
using namespace std;
struct sbttype{int l,r,w,s;}tr[N];
int a[N],tot=0,n,root=0;

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);
}

int getmax(int k){
    int p=k;
    while (tr[p].r!=0) p=tr[p].r;
    return tr[p].w;
}

int getmin(int k){
    int p=k;
    while (tr[p].l!=0) p=tr[p].l;
    return tr[p].w;
}

int main(){
      while (cin >> n){
        tot=0; root=0;
        long long ans=0;
        for (int i=1;i<=n;i++){
            int num;
            scanf("%d",&num);
            for (int j=1;j<=num;j++){
                int tmp;
                scanf("%d",&tmp);
                ins(root,tmp);
            }
            int tx=getmax(root),ty=getmin(root);
            ans+=(tx-ty);
            del(root,tx);
            del(root,ty);
        }
        cout << ans << endl;
      }
    return 0;
}

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 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;
}