。。（卧槽。。一不留神居然漏掉了这么多 CF 。。。得想办法先补上！。。）

Problem D. D. BerDonalds

Brief description:

求最小直径生成树的直径长度。。

Analysis:

同 https://www.shuizilong.com/house/archives/spoj-1479-the-gbaay-kingdom/）

http://codeforces.com/contest/266/submission/7909882

Problem E. More Queries to Array…

Brief description:

。。动态维护 N 个数 {An}。。。支持。。
= l r v: 区间修改，表示把区间 [l, r] 的数全部修改成 v。
? l r k：区间查询，查询区间 [l, r] 范围里的 \(\sum_{i=l}^{r} A[i] * (i – l + 1) ^ k\) 。

Analysis:

…线段树、二项式定理。。

。。做过 UPIT 的话都应该会 K = 1 的。。K 稍微大一点方法类似。。。显然对每个位置 i。。我们要维护 (i^k) A[i] 。。
。。。那么对我们要求的 \((i-l+1)^k A[i]\) 进行二项式展开。。得到。。
\[i^k + i^{k-1}(1-i) + i^{k-2}(1-i)^2 + \ldots + (1-i)^k \]
。。枚举里面的每一项。。。用线段树维护出来就行了。。。

http://codeforces.com/contest/266/submission/3009701

//}/* .................................................................................................................................. */

const int N = 100009, K = 6;
int C[K][K], S[N][K], A[N];

#define lx (x<<1)
#define rx (lx|1)
#define mid (l+r>>1)
#define lc lx, l, mid
#define rc rx, mid+1, r
#define root 1, 1, n

int vl[4*N][K], bj[4*N], a, b, v, k;

inline void apply(int x, int l, int r, int v){
    bj[x] = v; REP(i, K) vl[x][i] = pdt(dff(S[r][i], S[l-1][i]), v);
}

#define update REP(i, K) vl[x][i] = sum(vl[lx][i], vl[rx][i]);
#define release if (bj[x] != -1){       \
    apply(lc, bj[x]), apply(rc, bj[x]); \
    bj[x] = -1;                         \
}						                \

void Build(int x, int l, int r){
    bj[x] = -1;
    if (l == r) REP(i, K) vl[x][i] = pdt(A[l], pow(l, i)); //#
    else {
        Build(lc), Build(rc);
        update;
    }
}

void Modify(int x, int l, int r){
    if (r < a || b < l) return;
    if (a <= l && r <= b) apply(x, l, r, v);
    else {
        release;
        Modify(lc), Modify(rc);
        update;
    }
}

int Query(int x, int l, int r){
    if (r < a || b < l) return 0;
    if (a <= l && r <= b) return vl[x][k];
    else {
        release;
        return sum(Query(lc), Query(rc));
    }
}

int n, m;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

	RD(n, m); REP_1(i, n) RD(A[i]);
	REP(i, K){C[i][0] = 1; REP_1(j, i) C[i][j] = sum(C[i-1][j-1], C[i-1][j]);}
	REP_1(i, n) REP(j, K) S[i][j] = sum(S[i-1][j], pow(i,j));

    Build(root); char cmd; DO(m){
        
        RC(cmd); RD(a, b, v);

        if(cmd == '=') Modify(root);
        else{
            int res = 0, t = 1; FOR_1(i, 0, v){
                k = v - i; INC(res, pdt(Query(root), C[v][i], t));
                MUL(t, dff(1, a));
            }
            OT(res);
        }
    }
}

External link:

http://blog.csdn.net/shiqi_614/article/details/8534666

Posted by xiaodao
Category: Codeforces