NTUJ 1317 Another Easy but Not That Easy Problem

                                                                                                                                                                                                                       .
                                                                                                                                                                                                                       .





世界奇怪的題目耶，

Def f(a) = 1^x + 2^x + ... + a^x

可以知道f()應該是一個(x+1)次函式，

既然是(x+1)次咩，表示只要給定x+2個數字，就可以決定這個函式

這時候就用拉格朗日長直髮 不對 拉格朗日插值法，


而很巧妙的，如果我們帶的是f(1)~f(x+2)，盯著下面這個式子看

Σ bj * Π(a-ai)/(aj-ai)


會發現他變成


Σbj * [ (a-1)(a-2)...(a-(aj-1)) / (aj-1)! ] * [ (a-(aj+1))(a-(aj+2))...(a-(x+2)) / (x+2-aj)! ] * (-1)^(x+2-aj)


哇烏 這不就


Σbj [C(a-1)取(aj-1)] * [C(a-aj-1)取(x+2-aj)] * (-1)^(x+2-aj)


輕鬆愉快



總複雜度O(x)

NTUJ 1707 k-th number

恩沒錯，就是傳說中的經典的劃分樹。                                                                                                           .




其實超級好寫，只是兒子的區間要算好|||。

還有如果數字相同要處理一下，這個有點麻煩就是，還好這題保證沒有相同

網路上找得到許多教程，其實瞪著notonlysuccess的圖看幾秒就會領悟了

所以只是來備份代碼


#include <cstdio>
#include <cstring>
#include <algorithm>

#define MN 100010

int sorted[MN], val[20][MN], lcnt[20][MN];
int N, Q;

void build(int tl, int tr, int dep) {
    if(tl == tr) return ;
    int mid = (tl+tr)/2, pre = 0;
    int lc = tl, rc = mid+1;
    for(int i=tl; i<=tr; i++) {
        lcnt[dep][i] = pre;
        if(val[dep][i] <= sorted[mid]) {
            lcnt[dep][i] ++;
            val[dep+1][lc ++] = val[dep][i];
        }
        else val[dep+1][rc ++] = val[dep][i];
        pre = lcnt[dep][i];
    }
    build(tl, mid, dep+1);
    build(mid+1, tr, dep+1);
}

int query(int ql, int qr, int tl, int tr, int k, int dep) {
    if(tl == tr) return val[dep][tl];
    int mid = (tl+tr)/2, ql2L, qr2L, qinL;
    ql2L = lcnt[dep][ql] - (val[dep][ql]<=sorted[mid]);
    qr2L = lcnt[dep][qr];
    qinL = qr2L - ql2L;
    int newL, newR, newK;
    if(qinL >= k) {
        newL = tl + ql2L;
        newR = tl + qr2L - 1;
        newK = k;
        return query(newL, newR, tl, mid, newK, dep+1);
    }
    else {
        newL = mid + ql - tl - ql2L + 1;
        newR = mid + qr - tl - qr2L + 1;
        newK = k - qinL;
        return query(newL, newR, mid+1, tr, newK, dep+1);
    }

}

int main() {
    while(~scanf("%d%d", &N, &Q)) {
        for(int i=1; i<=N; i++) {
            scanf("%d", sorted+i);
            val[0][i] = sorted[i];
        }
        std::sort(sorted+1, sorted+1+N);
        build(1, N, 0);
        for(int i=1; i<=Q; i++) {
            int L, R, K;
            scanf("%d%d%d", &L, &R, &K);
            printf("%d\n", query(L, R, 1, N, K, 0));
        }
    }
}