牛客练习赛25

LL ac(int n)

{

    LL ans=0;

    for(int i=1,temp;i<=n;i=temp+1)

    {

        temp=n/(n/i);

        ans+=(n/i)*(temp-i+1);

    }

    return ans;

}

inline void upd(int &x, int y) { x < y && (x = y); }

const int N = 100005;

int n, m, tot;
int L[4 * N], R[4 * N], sum[4 * N], b[N];

void Pushup(int l, int r, int root) {
    int mid = (l + r) >> 1;

    L[root] = L[lson];
    if (L[lson] == mid - l + 1 && b[mid] < b[mid + 1]) L[root] += L[rson];

    R[root] = R[rson];
    if (R[rson] == r - mid && b[mid] < b[mid + 1]) R[root] += R[lson];

    sum[root] = max(sum[lson], sum[rson]);
    if (b[mid] < b[mid + 1]) upd(sum[root], L[rson] + R[lson]);

    //cout << root << " " << L[root] << " " << R[root] << " " << sum[root] << endl;
}

void Build(int l, int r, int root) {
    if (l == r) {
        int x; sc(x);
        b[++tot] = x;
        L[root] = R[root] = sum[root] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, lson);
    Build(mid + 1, r, rson);
    Pushup(l, r, root);
}

void Update(int l, int r, int root, int pos, int x) {
    if (l == r) {
        b[pos] = x;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) Update(l, mid, lson, pos, x);
    else Update(mid + 1, r, rson, pos, x);
    Pushup(l, r, root);
}



int main()
{
    sc(n), sc(m);
    Build(1, n, 1);
    int res = max(sum[1], max(L[1], R[1]));
    pr(res);

    res = 0;
    while(m--) {
        int pos, x;
        sc(pos), sc(x);
        Update(1, n, 1, pos, x);
        res = max(sum[1], max(L[1], R[1]));
        pr(res);
    }

    return 0;
}

const int N = 100005;
const LL mod = 1000000007;

int n, m;
LL a[N], s[N];

void Inite() {
    a[1] = 0;
    rep(i, 2, N) {
        if (i & 1) a[i] = ((n - 1) * a[i - 1] % mod - n + 1 + mod) % mod;
        else a[i] = ((n - 1) * a[i - 1] % mod + n - 1) % mod;
    }
}

int main()
{
    cin >> n >> m;

    Inite();

    LL sum = 0;
    Rep(i, 1, n) cin >> s[i], sum += s[i];

    sum %= mod;
    while(m--) {
        int x, t;
        sc(x), sc(t);
        if (!t) {
            printf("%lld\n", s[x]);
        }
        else {
            LL ans;
            if (t & 1) {
                ans = ((a[t] + 1) * sum % mod - s[x] + mod) % mod;
            }
            else {
                ans = ((a[t] - 1) * sum % mod + s[x]) % mod;
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}