bzoj 1558[JSOI 2009]等差数列

31971 ワード
データ構造とアルゴリズム php
転送ゲート:http://www.lydsy.com/JudgeOnline/problem.php?id=1558
【問題解】
この問題は気持ち悪いですね.の
ネット上の問題解の多くはコードを見てコードを見る.本当に無責任ですね.のここで詳しく話しましょう.の
問題解はコードの下にあります.

# include 
# include <string.h>
# include 
# include 
// # include 

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

# define RG register
# define ST static

int n, a[M], b[M];

struct pa {
    int s, ll, rr, sz;
    //   （      ），  ，   
    long long l, r;
    pa() {}
    pa(int s, int ll, int rr, int sz, long long l, long long r) : s(s), ll(ll), rr(rr), sz(sz), l(l), r(r) {}
    friend pa operator + (pa a, pa b) {
        pa c; int f = (a.r == b.l);
        c.s = a.s + b.s; c.sz = a.sz + b.sz;
        c.l = a.l, c.r = b.r;
        if(a.s == 0 && b.s == 0) {
            if(!f) c.ll = c.rr = c.sz;
            else {
                c.ll = a.ll-1;
                c.rr = b.rr-1;
                ++c.s;
            }
            return c;
        }
        if(a.s == 0) {
            c.rr = b.rr;
            if(!f) c.ll = a.sz + b.ll;
            else {
                c.ll = a.ll-1;
                if(b.ll > 0) c.s += (b.ll-1)/2 + 1;
            }
            return c;
        }
        if(b.s == 0) {
            c.ll = a.ll;
            if(!f) c.rr = a.rr + b.sz;
            else {
                c.rr = b.rr-1;
                if(a.rr > 0) c.s += (a.rr-1)/2 + 1;
            }
            return c;
        }
        
        c.ll = a.ll, c.rr = b.rr;
        
        if(a.rr == 0 && b.ll == 0) {
            if(f) --c.s; 
            return c;
        }        
        if(a.rr == 0) {
            if(f) c.s += (b.ll-1)/2;
            else c.s += b.ll/2;
            return c;
        }        
        if(b.ll == 0) {
            if(f) c.s += (a.rr-1)/2;
            else c.s += a.rr/2; 
            return c;
        }
        
        int d = (a.rr + b.ll)/2;
        if(f) d = min(d, 1 + (a.rr-1)/2 + (b.ll-1)/2);
        
        c.s += d;
        
        return c;
    }
};

namespace SMT {
    pa w[M];
    ll tag[M];
    # define ls (x<<1)
    # define rs (x<<1|1)
    inline void up(int x) {
        if(!x) return;
        if(!rs) {w[x] = w[ls]; return;}
        if(!ls) {w[x] = w[rs]; return;}
        w[x] = w[ls] + w[rs];
    }
    inline void pushtag(int x, ll d) {
        w[x].l += d, w[x].r += d;
        tag[x] += d;
    }
    inline void down(int x) {
        if(!x) return;
        if(!tag[x]) return;
        pushtag(ls, tag[x]);
        pushtag(rs, tag[x]);
        tag[x] = 0;
    }
    inline void build(int x, int l, int r) {
        tag[x] = 0;
        if(l == r) {
            w[x] = pa(0, 1, 1, 1, b[l], b[l]);
            return ;
        }
        int mid = l+r>>1;
        build(ls, l, mid);
        build(rs, mid+1, r);
        up(x);
    }
    inline void edt(int x, int l, int r, int L, int R, ll d) {
        if(L <= l && r <= R) {
            pushtag(x, d);
            return ;
        }
        down(x);
        int mid = l+r>>1;
        if(L <= mid) edt(ls, l, mid, L, R, d);
        if(R > mid) edt(rs, mid+1, r, L, R, d);
        up(x);
    }
    inline pa query(int x, int l, int r, int L, int R) {
        if(L <= l && r <= R) return w[x];
        down(x);
        int mid = l+r>>1;
        if(R <= mid) return query(ls, l, mid, L, R);
        else if(L > mid) return query(rs, mid+1, r, L, R);
        else return query(ls, l, mid, L, mid) + query(rs, mid+1, r, mid+1, R);
    }
    inline void debug(int x, int l, int r) {
        printf("x=%d, l=%d, r=%d:  sum = %d, size = %d, left = %d, right = %d, lnum = %lld, rnum = %lld
", x, l, r, w[x].s, w[x].sz, w[x].ll, w[x].rr, w[x].l, w[x].r);
        if(l==r) return;
        down(x);
        int mid = l+r>>1;
        debug(ls, l, mid);
        debug(rs, mid+1, r);
    }
}

int main() {
    int Q, l, r, a1, d;
    char opt[23];
    pa t;
    cin >> n;
    for (int i=1; i<=n; ++i) scanf("%d", a+i);
    for (int i=1; i1] - a[i];
//    for (int i=1; i
    cin >> Q;
    if(n == 1) {
        while(Q--) {
            scanf("%s", opt);
            if(opt[0] == 'A') scanf("%*d%*d%*d%*d");
            if(opt[0] == 'B') {scanf("%*d%*d"); puts("1");}
        }
        return 0;
    }
    SMT::build(1, 1, n-1);
//    SMT::debug(1, 1, n-1); 
    while(Q--) {
        scanf("%s", opt);
        if(opt[0] == 'A') {
            scanf("%d%d%d%d", &l, &r, &a1, &d);
            if(l != 1) SMT::edt(1, 1, n-1, l-1, l-1, a1);
            if(l <= r-1) SMT::edt(1, 1, n-1, l, r-1, d);
            if(r != n) SMT::edt(1, 1, n-1, r, r, -1ll * (r-l)*d - a1); 
        }
        if(opt[0] == 'B') {
            scanf("%d%d", &l, &r);
            if(l == r) puts("1");
            else {
                t = SMT::query(1, 1, n-1, l, r-1);
                int ans = (r-l+1+1)/2;
                if(t.s == 0) printf("%d
", ans);
                else {
                    ans = min(ans, t.s + (t.ll+1)/2 + (t.rr+1)/2);
                    printf("%d
", ans);
                }
            }
        }
//        SMT::debug(1, 1, n-1); 
    }
    return 0;
}

View Code
はい、ここです.ここは問題解です.
まず1段に等差数列を加える.これは線分ツリーで直接メンテナンスできますが、問い合わせの便宜上、線分ツリーメンテナンス差分グループを選択します.
例:
n=6, a[]={1,2,4,7,11,16}
ではメンテナンスはb[]={1,2,3,4,5},b[i]=a[i+1]-a[i]
b確立セグメントツリーについてメンテナンスを行う.
n=1に差がないことが分かったからです.特判を下す.
では,[a,b]に最初のa 1公差dを加えた等差数列を修正することを考える.私たちが維持しているのは差分グループなので、これはやりやすいです.
長いふりをすると、中間の部分差分が増加するのは公差d(前の+x+d、後の+x+d+d)である.
(この部分は自分で例を挙げて、自分で計算することができて、特に境界条件)、得られます:
修正:b[l-1]+=a 1,b[l...r-1]+=d,b[r]-=(r-l)*d+a 1
ここで判断する必要がある:もし私たちが区間を修正したら[1,?]、では、b[l-1]は変更する必要はありません.最初の場所には差分がないからです.
区間[x,x]を修正すれば,2番目の修正は必要ない.などなど.
3番目の減少は、後の差分を安定に維持するためであり、a[r]+=(r-l)*d+a 1が容易に見られるため、a[r+1]-a[r]は(r-1)*d+a 1を減少させる
議論が終わったら、質問を始めましょう.
求められるのは,最低何個の等差数列セグメントに分けるかを尋ねる.セグメントなので、連続的で、シーケンスよりずっとやりやすいです.
これは[l,r]区間の差分数群がどれだけ連続するセグメントがあるかを単純に求める問題ではない.
なぜなら、例えば簡単な例です.
差分数群はb[]={1,2,3,4},a[]={x,x+1,x+3,x+6,x+10}である.
では、答えは4段ではなく、3段です.なぜですか.{x,x+1}と{x+3,x+6}と{x+10}はいずれも等差であるため,2つの数が等差を構成する場合を判断する.
だから私たちはもっと物を守らなければなりません.
まず、1つの区間の中間部分がどの等差数列であるかを決定すれば、後で変更されないことが決定される.
私たちは維持しています
1.区間の等差数列セグメント数.
2.区間左に残った分散数の個数と、右に残った分散数の個数
3.区間左の数は何ですか、区間右の数は何ですか
4.区間の大きさ.
区間を[l,r]と仮定すると、最後の答えはセグメントツリークエリ[l,r-1](差分が過ぎたので-1)が出てきた後です.
1.(r-l+1+2)/2(r-l+1は区間長であり、この分法は2つの数2つの数分である)
2.質問された区間における等差数列の段数に区間左に残った分散数を加えた個数と、右に残った分散数の個数を1つの方法で等差数列の個数に分けるかのどちらかである.
両辺の個数がどのようにセグメントに対応するかについては,いくつかの例を描くことで解決できる.
では、セグメントツリー内とクエリーを考慮すると、データがマージされます.
 1 struct pa {
 2     int s, ll, rr, sz;
 3     //   （      ），  ，   
 4     long long l, r;
 5     pa() {}
 6     pa(int s, int ll, int rr, int sz, long long l, long long r) : s(s), ll(ll), rr(rr), sz(sz), l(l), r(r) {}
 7     friend pa operator + (pa a, pa b) {
 8         pa c; int f = (a.r == b.l);
 9         c.s = a.s + b.s; c.sz = a.sz + b.sz;
10         c.l = a.l, c.r = b.r;
11         if(a.s == 0 && b.s == 0) {
12             if(!f) c.ll = c.rr = c.sz;
13             else {
14                 c.ll = a.ll-1;
15                 c.rr = b.rr-1;
16                 ++c.s;
17             }
18             return c;
19         }
20         if(a.s == 0) {
21             c.rr = b.rr;
22             if(!f) c.ll = a.sz + b.ll;
23             else {
24                 c.ll = a.ll-1;
25                 if(b.ll > 0) c.s += (b.ll-1)/2 + 1;
26             }
27             return c;
28         }
29         if(b.s == 0) {
30             c.ll = a.ll;
31             if(!f) c.rr = a.rr + b.sz;
32             else {
33                 c.rr = b.rr-1;
34                 if(a.rr > 0) c.s += (a.rr-1)/2 + 1;
35             }
36             return c;
37         }
38         
39         c.ll = a.ll, c.rr = b.rr;
40         
41         if(a.rr == 0 && b.ll == 0) {
42             if(f) --c.s; 
43             return c;
44         }        
45         if(a.rr == 0) {
46             if(f) c.s += (b.ll-1)/2;
47             else c.s += b.ll/2;
48             return c;
49         }        
50         if(b.ll == 0) {
51             if(f) c.s += (a.rr-1)/2;
52             else c.s += a.rr/2; 
53             return c;
54         }
55         
56         int d = (a.rr + b.ll)/2;
57         if(f) d = min(d, 1 + (a.rr-1)/2 + (b.ll-1)/2);
58         
59         c.s += d;
60         
61         return c;
62     }
63 };

上記のコードは、セグメントツリー内の構造体とどのように結合するかを見てみましょう.
まずsz,l,rはすべて直接合併します.
そして考えなければならないのはllとrrとsがどのように合併するかという問題です.
左/右に連続セグメントがない問題を先に処理します(いずれもばらばらです)
3種類に分けます:すべてなくて、左はなくて、右はありません
この部分は直接見て、11~37行です
左/右に連続セグメントがあります.処理するのは次のとおりです.
左側のセグメントが境界に隣接している場合、すなわちll=0またはrr=0の場合である.
3種類に分けます:a.rr=0&&b.ll=0,a.rr=0,b.ll=0
第1のクラスは明らかに2つのセグメントがa.r=b.lであれば直接1つのセグメントに合併することができ、そうでなければ正常に合併し、41~44行目である.
後の2種類は、a.r=b.lの場合、残りの1つ(0より大きいb.llまたはa.rr)で1つ少ない数で区切ることができます.45~54行目です.
そうでなければ、正常な区分方法に従います:すべて2つ2つに区分するか、中間の等しいものを提出して、左右に区分します.
議論するのがおっくうで、きっと優れているかどうか.のminを取りましょう
そして…ってやっと言った
 
この問題はいいですね.の細部は盗人が多い
 
転載先:https://www.cnblogs.com/galaxies/p/bzoj1558.html
nyoj 248 BUYING FEED(欲張りorDP)
Visual Studio デバッグモードが止まらない