[SHOI2015]脑洞治疗仪

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

using namespace std;

const int N = 200010;

struct SegTree {
    int l, r;
    int len, sum, lmax, rmax, tmax, tag;
} tr[N << 2];

int n, m;

void pushup(int u) {
    SegTree lson = tr[u << 1], rson = tr[u << 1 | 1];
    tr[u].sum = lson.sum + rson.sum;
    if (lson.lmax == lson.len) tr[u].lmax = lson.len + rson.lmax;
    else tr[u].lmax = lson.lmax;
    if (rson.rmax == rson.len) tr[u].rmax = rson.len + lson.rmax;
    else tr[u].rmax = rson.rmax;
    tr[u].tmax = max(max(lson.tmax, rson.tmax), lson.rmax + rson.lmax);
}

inline void down(int tag, int u) {
    if (tag == 1) {
        tr[u].tmax = tr[u].lmax = tr[u].rmax = tr[u].len;
        tr[u].sum = 0;
        tr[u].tag = 1;
    }
    else {
        tr[u].tmax = tr[u].lmax = tr[u].rmax = 0;
        tr[u].sum = tr[u].len;
        tr[u].tag = 2;
    }
}

void pushdown(int u) {
    if (tr[u].tag == 1) {
        down(1, u << 1), down(1, u << 1 | 1);
        tr[u].tag = 0;
    }
    else if (tr[u].tag == 2) {
        down(2, u << 1), down(2, u << 1 | 1);
        tr[u].tag = 0;
    }
}

void build(int u, int l, int r) {
    tr[u] = {l, r, r - l + 1, 0, 0, 0, 0, 0};
    if (l == r) tr[u].sum = 1;
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int type) {
    if (tr[u].l >= l && tr[u].r <= r) {
        if (type == 1) down(1, u);
        else if (type == 2) down(2, u);
    }
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, type);
        if (r > mid) modify(u << 1 | 1, l, r, type);
        pushup(u);
    }
}

int query0(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].tmax;
    else {
        pushdown(u);
        int res = 0;
        if (tr[u << 1 | 1].l > r) res = query0(u << 1, l, r);
        else if (tr[u << 1].r < l) res = query0(u << 1 | 1, l, r);
        else res = max(max(query0(u << 1, l, r), query0(u << 1 | 1, l, r)), min(tr[u << 1].rmax, tr[u << 1 | 1].l - l) + min(tr[u << 1 | 1].lmax, r - tr[u << 1].r));
    }
}

int query1(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int sum = 0;
        if (l <= mid) sum = query1(u << 1, l, r);
        if (r > mid) sum += query1(u << 1 | 1, l, r);
        return sum;
    }
}

int query2(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].len - tr[u].sum;
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int _sum = 0;
        if (l <= mid) _sum = query2(u << 1, l, r);
        if (r > mid) _sum += query2(u << 1 | 1, l, r);
        return _sum;
    }
}

void solve(int l0, int r0, int l1, int r1) {
    int bound = query1(1, l0, r0);
    if (!bound) return;
    modify(1, l0, r0, 1);

    int l = l1, r = r1;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (query2(1, l1, mid) <= bound) l = mid;
        else r = mid - 1;
    }
    modify(1, l1, l, 2);
}

int main() {
    scanf("%d%d", &n, &m);

    build(1, 1, n);

    int op;
    while (m--) {
        scanf("%d", &op);
        if (!op) {
            int l, r;
            scanf("%d%d", &l, &r);
            modify(1, l, r, 1);
        }
        else if (op == 1) {
            int l0, r0, l1, r1;
            scanf("%d%d%d%d", &l0, &r0, &l1, &r1);
            solve(l0, r0, l1, r1);
        }
        else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", query0(1, l, r));
        }
    }

    return 0;
}

SHOI2017 相逢是问候

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

using namespace std;

typedef long long LL;

const int N = 50010, LIM = 60;

struct SegTree {
    int l, r;
    int minv, sum;
} tr[N << 2];

int n, m, p, c;
int a[N][LIM];

inline int Mod(LL n,int p) { return n >= p ? (n % p + p) : n; }

int rd() {
    int x = 0, s = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') s = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * s;
}

int calcphi(int n) {
    int res = n;
    for (int i = 2; i <= n / i; i++) 
        if (!(n % i)) {
            res = res / i * (i - 1);
            while (!(n % i)) n /= i;
        }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

int phi[LIM], pcnt, c1[LIM][1 << 15], c2[LIM][1 << 15];

void init() {
    phi[pcnt = 0] = p;
    while (phi[pcnt] > 1) pcnt++, phi[pcnt] = calcphi(phi[pcnt - 1]);

    for (int i = 0; i <= pcnt; i++) {
        c1[i][0] = c2[i][0] = 1;
        for (int j = 1; j < 1 << 15; j++)
            c1[i][j] = Mod((LL)c1[i][j - 1] * c, phi[i]);
        c2[i][1] = Mod((LL)c1[i][(1 << 15) - 1] * c, phi[i]);
        for (int j = 2; j < 1 << 15; j++)
            c2[i][j] = Mod((LL)c2[i][j - 1] * c2[i][1], phi[i]);
    }
}

inline int power(int n, int i) {
    return Mod((LL)c1[i][n & 32767] * c2[i][n >> 15], phi[i]);
}

int solve(int a, int depth, int i) {
    if (!depth) return Mod(a, phi[i]);
    if (i == pcnt) return c ? 1 : 0;
    return power(solve(a, depth - 1, i + 1), i);
}

inline void pushup(int u) {
    tr[u].minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv);
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    if (tr[u].sum >= p) tr[u].sum -= p;
}

void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if (l == r) tr[u].sum = a[l][0];
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r) {
    if (tr[u].minv > pcnt) return;
    if (tr[u].l == tr[u].r) {
        tr[u].minv++;
        tr[u].sum = a[tr[u].l][tr[u].minv];
        return;
    } 
    if (tr[u].l >= l && tr[u].r <= r) {
        modify(u << 1, l, r), modify(u << 1 | 1, l, r);
        pushup(u);
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r);
    if (r > mid) modify(u << 1 | 1, l, r);
    pushup(u);
}

int ans;

void query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        ans = (ans + tr[u].sum >= p) ? (ans + tr[u].sum - p) : (ans + tr[u].sum); 
        return;
    }
    else {
        int v = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) query(u << 1, l, r);
        if (r > mid) query(u << 1 | 1, l, r);
    }
}

int main() {
    n = rd(), m = rd(), p = rd(), c = rd();

    init();

    for (int i = 1; i <= n; i++) {
        a[i][0] = rd();
        for (int j = 1; j <= pcnt + 1; j++)
            a[i][j] = solve(a[i][0], j, 0) % p;
        a[i][0] %= p;
    }

    build(1, 1, n);

    int op, l, r;
    while (m--) {
        op = rd(), l = rd(), r = rd();
        if (!op) modify(1, l, r);
        else {
            ans = 0;
            query(1, l, r);
            printf("%d\n", ans);
        }
    }

    return 0;
}