BZOJ 4408:[Fjoi 2016]謎の数(持続可能な線分ツリー)

5730 ワード

持続可能なデータ構造 BZOJ

タイトルの説明
http://www.lydsy.com/JudgeOnline/problem.php?id=4408
最小であることを求めて1段の区间の中でいくつかの数の和に表すことができない数.(やはり問題面を見ましょう)
構想
線分ツリーの問題を永続化できます.ところで、どうして私は長く打つことができて、いつも鶏を食べることができます.の
まず表示できる区間を[1,x]とすると,神秘数はx+1となる.現在1つの数yを加えて、2つの状況に分けます.
①y<=x+1で表示できる区間は[1,x+y]、神秘数はx+y+1となる.
②y>x+1ではx+1は表示されず、表示できる区間は変わらず、神秘数は変わらない.
そこで私たちは区間の和を維持します.神秘数をansとし,最初はans=1とする.区間の中でans以下の数を見つけて和を求め,Getと記す.Get>=ansの場合,区間は[1,Get],ans=Get+1に拡張できる.
Getこの問題の不思議なところはy>x+1のyが神秘数に何の影響も与えず、ニャーはy<=x+1のyが一度に答えを更新することができる.
一方、ある数以下の区間を探して、持続可能なセグメントツリーで維持できます.すなわち、各ポイントの重み値セグメントツリーのチェーンを開き、接頭辞和を維持すればよい.
時間logNを尋ねるたびにansが少なくとも2倍になるので,総時間はO(nlogN+mlogNlogN)である.
コード#コード#

#include 
#define maxn 100010
#define Lg 32

using namespace std;

int a[maxn], n, m, cnt, ToT, ans, Get;

struct Tnode{
    Tnode *lson, *rson;
    int sum;
}tree[maxn*Lg], *Root[maxn];

Tnode *NewTnode(){
    tree[cnt].lson = tree[cnt].rson = tree;
    tree[cnt].sum = 0;
    return tree+cnt++;
}

void Update(Tnode *root, int L, int R, int x){
    if(L == R){
        root->sum += x;
        return;
    }

    int mid = (L + R) >> 1;
    Tnode *p = NewTnode();

    if(x <= mid){
        *p = *(root->lson);
         root->lson = p;
         Update(p, L, mid, x);
    }
    else{
        *p = *(root->rson);
        root->rson = p;
        Update(p, mid+1, R, x);
    }

    root->sum = root->lson->sum + root->rson->sum;
}

int Query(Tnode *root1, Tnode *root2, int L, int R, int x){
    if(L == R)  return root2->sum - root1->sum;

    int mid = (L + R) >> 1;
    if(x <= mid)  return Query(root1->lson, root2->lson, L, mid, x);
    else  return root2->lson->sum - root1->lson->sum + Query(root1->rson, root2->rson, mid+1, R, x);
}

int main(){

    scanf("%d", &n);
    for(int i = 1; i <= n; i++)  scanf("%d", &a[i]), ToT += a[i];

    Root[0] = NewTnode();
    for(int i = 1; i <= n; i++){
        Root[i] = NewTnode();
        *Root[i] = *Root[i-1];
        Update(Root[i], 1, ToT, a[i]);
    }

    scanf("%d", &m);

    int l, r;
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &l, &r);
        ans = 1;
        for(;;){
            Get = Query(Root[l-1], Root[r], 1, ToT, ans);
            if(Get < ans)  break;
            ans = Get + 1;
        }
        printf("%d
", ans);
    }

    return 0;
}

JAVAで南開百題をやってみるつもりです(四)

6、jQueryのAjaxとJavaはPOST方式で対話する