WUST 1255チョコレート(線分樹のシングルポイント区間更新クエリ)

4093 ワード

ACM データ構造線分樹

1355:チョコレート
Time Limit: 1セット
メモリLimit: 128 MB
64 bit IO Format: %lld
Submitted: 190
Acceepted: 26
[Submit][Sttus][Web Board]
Description
TYが一番好きなことはチョコレートを食べることです.食べきれないチョコレートを持つことを常に幻想しています.acmerとして、IcYが問題を出して彼女を試験するつもりです.答えたら、チョコレートは自然にどんどん増えてきます.
IcYは一列に並んだチョコレートを与えました.あるものは徳芙、あるものはフェレロで、それらは全部違った美味しい値を持っています.今はIcYは魔法でこれらのチョコレートを変えました.TYはランキングのK番目がチョコレートの美味しい値であることを指摘しなければなりません.今、TYはあなたの助けを求めにきます. TYはチョコレートを食べますか?
Input
入力データは多くのグループがあり、EOFで終了します.
各グループのデータの最初の行は2つの整数N、Mです.Nは初期のチョコレートの数を表し、Mは動作数を表します.
二番目の行はn個の正の整数を含み、各ブロックのチョコレートの美味しい値wiを表します.各ブロックのチョコレートの下に0-n-1が表示されます.
次のM行はM個の操作を表します.
操作は4種類あります
Query x y ある区間の美味しいものを検索する最大値を表します.
Ask x あるチョコレートの美味しいものを調べます.
Change x y 代表的にx番目のブロックの美味しい値をyに変えます.
Add x y 代表的にはx番目からy番目のチョコレートまでの美味しい値がそれぞれ1.
(1 <= N<= 100000   1<= M <= 100000   Wi <= 5000 )
Output
Queryごとに1つの整数を出力すると、区間内の美味しいものの最大値を表します.
Askごとにこのチョコレートの美味しい値を表して整数を出力します.
Sample Input

10 4
1 2 3 4 5 6 7 8 9 10
Ask 0
Change 0 1
Add 0 2
Query 0 2

Sample Output

1
4

[Submit][Sttus][Web Board]
クイズ:
これは私達の学校のojの問題です.趙さんはたくさんの人にtleを見てやらせてくれました.初めての配列は小さいです.TLEについて変えたら終わりました.考察の基礎はまだあります.lazy(そうでないとタイムアウトします.線分樹のテーマを経験したことがある私にとって、この問題は水のhhhhです.500 ms過ぎたのです.)
コード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define M (t[k].l+t[k].r)/2
#define lson k*2
#define rson k*2+1
using namespace std;
struct node
{
    int l,r;
    int maxx;//    
    int tag;//    
}t[100005*4];
void pushup(int k)//    ，    
{
    t[k].maxx=max(t[lson].maxx,t[rson].maxx);
}
void Build(int l,int r,int k)//    
{
    t[k].l=l;
    t[k].r=r;
    t[k].tag=0;
    if(l==r)
    {
        scanf("%d",&t[k].maxx);
        return;
    }
    int mid=M;
    Build(l,mid,lson);
    Build(mid+1,r,rson);
    pushup(k);
}
void pushdown(int k)//    
{
    if(t[k].tag)
    {
        t[lson].maxx+=t[k].tag;
        t[rson].maxx+=t[k].tag;
        t[lson].tag+=t[k].tag;
        t[rson].tag+=t[k].tag;
        t[k].tag=0;
    }
}
void update1(int l,int r,int k,int v)//        
{
    if(t[k].l==l&&t[k].r==r)
    {
        t[k].maxx+=v;
        t[k].tag+=v;
        return;
    }
    pushdown(k);
    int mid=M;
    if(r<=mid)
        update1(l,r,lson,v);
    else if(l>mid)
        update1(l,r,rson,v);
    else
    {
        update1(l,mid,lson,v);
        update1(mid+1,r,rson,v);
    }
    pushup(k);
}
void update2(int x,int k,int v)//        
{
    if(t[k].l==t[k].r)
    {
        t[k].maxx=v;
        return;
    }
    pushdown(k);
    int mid=M;
    if(x<=mid)
        update2(x,lson,v);
    else
        update2(x,rson,v);
    pushup(k);
}
int query1(int l,int r,int k)//        
{
    if(t[k].l==l&&t[k].r==r)
    {
        return t[k].maxx;
    }
    pushdown(k);
    int mid=M;
    if(r<=mid)
        return query1(l,r,lson);
    else if(l>mid)
        return query1(l,r,rson);
    else
    {
        return max(query1(l,mid,lson),query1(mid+1,r,rson));
    }
}
int query2(int x,int k)//        
{
    if(t[k].l==t[k].r)
    {
        return t[k].maxx;
    }
    pushdown(k);
    int mid=M;
    if(x<=mid)
        return query2(x,lson);
    else
        return query2(x,rson);
}
int main()
{
    int n,m,i,j,x,y,z;
    char s[10];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Build(0,n-1,1);
        for(i=0;iy)
                    swap(x,y);
                update1(x,y,1,1);
            }
            else
            {
                scanf("%d%d",&x,&y);
                if(x>y)
                    swap(x,y);
                printf("%d
",query1(x,y,1));
            }
        }
    }
    return 0;
}

データ構造10進数から2進数への変換(シーケンススタックの設計と応用)