冬休み合宿ログ(七)——データ構造

22564 ワード

今日の主な内容:1.RMQアルゴリズム
　　　　　　　　　2.ツリー配列
　　　　　　　　　3.セグメントツリー
(一)RMQアルゴリズム
A - RMQ
Time Limit:5000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.
Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.
Input
Line 1: Two space-separated integers,
N and
Q.
Lines 2..
N+1: Line
i+1 contains a single integer that is the height of cow
i
Lines
N+2..
N+
Q+1: Two integers
A and
B (1 ≤
A ≤
B ≤
N), representing the range of cows from
A to
B inclusive.
Output
Lines 1..
Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.
Sample Input

Sample Output

6
3
0

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>

using namespace std;
typedef long long LL;
const int maxN = 200010;

int f1[maxN][32];
int f2[maxN][32];
int n,q;
int logN[maxN];

int Max(int a, int b){
    return a>b?a:b;
}
int Min(int a, int b){
    return a>b?b:a;
}
void init(){
    memset(logN, 0, sizeof(logN));
    for(int i=0 ;i<maxN; ++i){
        for(int j= 0 ;j<32; ++j){
            f1[i][j]=0; f2[i][j]=0;
        }
    }
}

void init_RMQ(){
    logN[1]= 0;
    for(int i =2 ;i<=maxN;++i){
        logN[i] =((i&(i-1))==0)?logN[i-1]+1:logN[i-1];
    }
    for(int j=1; j<=logN[n]; ++j){
        for(int i=1; i+(1<<j)-1<=n;++i){
            f1[i][j] = Max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
        }
    }
    for(int j=1; j<=logN[n];++j){
        for(int i=1; i+(1<<j)-1<=n;++i){
            f2[i][j] = Min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
        }
    }
}

int ANS(int x, int y){
    int k = logN[y-x+1];
    return Max(f1[x][k],f1[y-(1<<k)+1][k]) - Min(f2[x][k],f2[y-(1<<k)+1][k]);
}
int main(){
    scanf("%d %d",&n,&q);
    init();
    for(int i=1 ;i<=n;++i){
        scanf("%d",&f1[i][0]);
        f2[i][0] =f1[i][0];
    }
    init_RMQ();
  /*  for(int i=0 ;i<=n;++i){
        for(int j=0 ;j<logN[n];++j)
            cout<<f[i][j]<<" ";
        cout<<endl;
        }*/
    for(int j=1; j<=q; ++j){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d
",ANS(a,b));
    }
}

(二)樹状配列
超牛逼のアルゴリズムはいいですか!!!このような方法を創造する人の頭がどのように長いことを知りません!!!
覚えていなければ見てもいいです.http://blog.csdn.net/int64ago/article/details/7429868
B-ツリー配列or線分ツリー
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
C国の死対頭A国はこの間軍事演習を行っていたので、C国のスパイの頭のDerekと彼の部下のTidyはまた忙しくなった.A国は海岸線に沿って直線的にN個の工兵キャンプを配置し、DerekとTidyの任務はこれらの工兵キャンプの活動状況を監視することである.ある種の先進的な監視手段を採用したため、各工兵キャンプの人数C国が把握しているのははっきりしていて、各工兵キャンプの人数が変動する可能性があり、数人の人手を増加したり減らしたりする可能性があるが、これらはC国の監視から逃れられない.
中央情報局は敵がどのような戦術を演習しているのかを研究しなければならないので、TidyはいつでもDerekにある連続した工兵キャンプが全部で何人いるかを報告しなければならない.例えば、Derekは「Tidy、すぐに3番目のキャンプから10番目のキャンプまで何人いるかを報告しなさい」と聞いた.Tidyはすぐにこの段落の総人数を計算して報告しなければならない.しかし、敵兵キャンプの人数は常に変動し、Derekは尋ねるたびにセグメントが異なるので、Tidyは毎回1つずつキャンプの数を数えなければならず、すぐに疲れ果ててしまいました.DerekはTidyの計算速度にますます不満を持っています:“あなたは死んで太っていて、計算がこんなに遅いので、私はあなたを首にします!”Tidyは考えます:“あなたは自分で計算してみて、これは本当に疲れた仕事です!私はあなたが私を首にすることを憎んでいます!”仕方なく、Tidyはコンピュータの専門家Windbreakerに電話して助けを求めるしかなかった.Windbreakerは言った.「死んだデブ、普段acmの問題をたくさん作って、アルゴリズムの本をたくさん読んで、今は苦果を味わったでしょう.」ティディは「私は間違っていることを知っています...」と言った.しかし、Windbreakerはもう電話を切った.Tidyは悩んでいます.これで彼は本当に崩壊します.賢い読者、プログラムを書いて彼にこの仕事を完成させることができますか.しかし、プログラムの効率が足りなければ、TidyはDerekに叱られます.

Input
1行目の整数Tは、Tグループのデータがあることを示す.
各グループのデータの最初の行には正の整数N(N<=50000)があり、敵にはN個の工兵キャンプがあり、次にはN個の正の整数があり、i個目の正の整数aiはi個目の工兵キャンプの開始時にai人がいることを示している(1<=ai<=50).
次に、各行に1つのコマンドがあります.コマンドには4つの形式があります.
(1)Add i j,i,jは正の整数であり,i番目のキャンプにj個人が増加したことを示す(jは30を超えない)
(2)Sub i j,i,jは正の整数であり、i番目のキャンプがj個人を減少させることを示す(jは30を超えない).
(3)Query i j,i,jは正の整数であり、i<=jであり、i番目からj番目のキャンプに尋ねる総人数を表す.
(4)Endは終了を示し、このコマンドは各グループのデータの最後に現れる.
データのセットあたり最大4,000個のコマンド

Output
i番目のグループのデータに対して、まず「Case i:」とリターンを出力し、
Queryクエリごとに整数を出力して車に戻り,クエリのセグメントの総数を表し,この数はint以内に保たれる.

Sample Input
1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End

Sample Output
Case 1: 6 33 59

//         strcmp   
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>

using namespace std;
typedef long long LL;
const int maxN = 50010;

int N;
int tree[maxN];

int lowbit(int x){
    return x&-x;
}

void add(int k, int num){
    while(k<=N){
        tree[k]+=num;
        k+=lowbit(k);
    }
}

LL sum(int k){
    LL ans = 0;
    while(k){
        ans+=tree[k];
        k-=lowbit(k);
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int i=1; i<=T;++i){
        memset(tree,0,sizeof(tree));
        printf("Case %d:
",i);
        scanf("%d", &N);
        for(int i = 1 ; i<=N; ++i){
            int num;
            scanf("%d",&num);
            add(i,num);
        }
        char s[10];
        memset(s,0,sizeof(s));
        while(scanf("%s",s)!=EOF){
            if(!strcmp(s,"End"))    break;
            if(!strcmp(s,"Add")){
                int a, b;
                scanf("%d%d", &a, &b);
                add(a,b);
            }
            if(!strcmp(s,"Sub")){
                int a, b;
                scanf("%d%d", &a, &b);
                add(a,-b);
            }
            if(!strcmp(s,"Query")){
                int a, b;
                scanf("%d%d", &a, &b);
                printf("%lld
", sum(b)-sum(a-1));
            }
        }
    }
    return 0;
}

(三)線分樹
二分アルゴリズムに似ています.
本質は区間更新のLazy配列にある.
2つの比較的に良いブログを回転します:1.http://blog.sina.com.cn/s/blog_a2dce6b30101l8bi.html
２．http://blog.csdn.net/acceptedxukai/article/details/6933446
C-線分ツリー単点更新
Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.
これは多くの学生に反感を抱かせた.
あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.

Input
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.
各試験の第1行には、2つの正の整数NおよびM(0学生ID番号はそれぞれ1編からNまでです.
2行目はN個の整数を含み、このN個の学生の初期成績を表し、i番目の数はIDがiの学生の成績を表す.
次はM行です.各行には1文字C('Q'または'U'のみ)と2つの正の整数A,Bがある.
Cが「Q」である場合、IDがAからB(A,Bを含む)までの学生の中で、成績が最も高いかを尋ねる質問操作であることを示す.
Cが「U」の場合、IDがAの学生の成績をBに変更する更新操作であることを示す.

Output
問合せ操作ごとに、1行に最高成績を出力します.

Sample Input
5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5

Sample Output
5 6 5 9
Hint

Huge input,the C function scanf() will work better than cin

//          ，             scanf("%c")   ，  ，scanf("%d,&tree[root])    ＆  ，      ，       
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;

const int maxN = 800005;
const int INF = 0;
int tree[maxN];

void build_tree(int left, int right, int root){
    if(left==right){
        scanf("%d",&tree[root]);
        return ;
    }
    int mid = (left+right)>>1;
    build_tree(left,mid,root<<1);
    build_tree(mid+1,right,root<<1|1);
    tree[root] = max(tree[root<<1],tree[root<<1|1]);
}

void update(int id, int grade, int left, int right, int root){
    if(left==right){
        tree[root] = grade;
        return ;
    }
    int mid = (left+right)>>1;
    if(id<=mid)  update(id,grade,left,mid,root<<1);
    else        update(id,grade,mid+1,right,root<<1|1);
    tree[root] = max(tree[root<<1], tree[root<<1|1]);
}

int Query(int tleft, int tright, int left, int right, int root){
    if(tleft<=left && tright>=right){
        return tree[root];
    }
    else{
        int ans = INF;  int mid = (left+right)>>1;
        if(tleft<=mid)  ans= max(ans, Query(tleft,tright,left,mid,root<<1));
        if(tright>mid) ans= max(ans, Query(tleft,tright,mid+1,right,root<<1|1));
        return ans;
    }

}
int main(){
    int n, m;
    while(scanf("%d %d", &n, &m)!=EOF){
        build_tree(1,n,1);
        while(m--){
            int a, b;
            char s[3];
            scanf("%s%d%d", s, &a, &b);
            if(s[0]=='Q'){
                printf("%d
", Query(a,b,1,n,1));
            }
            if(s[0]=='U')
            update(a,b,1,n,1);
        }
    }
    return 0;
}

D-セグメントツリー区間更新
Time Limit:5000MS Memory Limit:131072KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
次の2つの質問を処理する必要があるシーケンスが示されています.
「C a b c」は、[a,b]区間に与えられた値がすべてc(−1000≦c≦10000)増加したことを示す.
「Q a b」は、[a,b]区間のすべての値の和を尋ねる.
Input
第1行は2つの整数N,Qを含む.1 ≤ N,Q ≤ 100000.
2行目には、初期シーケンスA(−1000000000≦Ai≦10000000)を表すn個の整数が含まれる.
次のQ行は、タイトルの説明のようにフォーマットされています.
Output
Qの冒頭の質問ごとに、対応する答えを出力し、各答えの行を出力する必要があります.
Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;

const int maxN = 500005;

LL sum[maxN], add[maxN];

struct node{
    int l, r;
    int mid(){
        return (l+r)>>1;
    }
}tree[maxN];

void PushUp(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void PushDown(int rt, int m){
    if(add[rt]){
        add[rt<<1] += add[rt];
        add[rt<<1|1] += add[rt];
        sum[rt<<1] +=   add[rt]*(m - (m>>1));
        sum[rt<<1|1] += add[rt]*(m>>1);
        add[rt] = 0;
    }
}

void build (int l, int r, int rt){
    tree[rt].l = l ;
    tree[rt].r = r ;
    add[rt] = 0;
    if(l == r){
        scanf("%lld", &sum[rt]);
        return ;
    }
    int m = tree[rt].mid();
    build(l,m, rt<<1);
    build(m+1, r, rt<<1|1);
    PushUp(rt);
}

void update(int c, int l, int r, int rt){
    if(tree[rt].l ==l && tree[rt].r ==r){
        add[rt] += c;   sum[rt] += c*(r-l+1) ; //cichu
        return ;
    }
    if(tree[rt].l == tree[rt].r)    return ;
    PushDown(rt, tree[rt].r - tree[rt].l +1);
    int m = tree[rt].mid();
    if( r<= m)  update(c, l, r, rt<<1);
    else if(l > m)    update(c, l, r, rt<<1|1);
    else{
        update(c, l, m, rt<<1);
        update(c, m+1, r, rt<<1|1);
    }
    PushUp(rt);
}

LL query(int l, int r, int rt){
    if(l == tree[rt].l && r==tree[rt].r){
        return sum[rt];
    }
    PushDown(rt, tree[rt].r - tree[rt].l +1);
    int m = tree[rt].mid();
    LL res = 0 ;
    if(r<=m)    res+= query(l, r, rt<<1);
    else if(l>m)    res+=   query(l, r, rt<<1|1);
    else {
        res +=  query(l, m, rt<<1);
        res +=  query(m+1, r, rt<<1|1);
    }
    return res;
}
int main(){
    int n, m;
    while(scanf("%d %d", &n, &m)!=EOF){
        build(1,n,1);
        while(m--){
            char ch[2];
            scanf("%s", ch);
            int a, b, c;
            if(ch[0] == 'Q'){
                scanf("%d %d", &a, &b);
                printf("%lld
", query(a, b, 1));
            }
            else {
                scanf("%d %d %d", &a, &b, &c);
                update(c, a, b, 1);
            }
        }
    }
    return 0;
}

C#の暗号解読(情報セキュリティ)コードパッケージ

bmhアルゴリズム