头像

这个显卡不太冷


访客:26461

离线:2天前



原题传送门

题意是有Q个区间询问,每次询问只能得到区间内未被覆盖的位置。
要求一种顺序,使得这Q个询问里的最小值最大。

必须首先发现:最后一个人所得到的座位数量,和前面Q-1个询问的顺序是没有关系的。
所以可以得到一个贪心策略:
1. 从最后一个人开始,枚举谁能得到最多的座位。假设是第X个询问。
2. 去掉第X个询问,再重复步骤一。
3. 重复以上步骤直到询问为空。从得到的答案里取一个最小值即是答案。

如果每一步都暴力枚举,离散化以后复杂度是$O(Q^2)$的(排序以后扫描)。
可以建立一颗长度为N的线段树,线段树上每个点存储当前区间被哪些询问完全覆盖,和区间内点的最少覆盖次数。
考虑到执行覆盖和撤销覆盖的操作都是成对出现的,当前线段被哪些区间完全覆盖可以不用下传懒标记,参考 亚特兰蒂斯 的做法。在往下走的时候,仅仅对第一次遇见的区间进行标记,撤销的时候也无需往下走。
以样例来解释,仅需要在这些有颜色的区间上记录有哪些线段对其进行了覆盖即可。

区间最小值就用普通的懒标记,优化到每次修改是$NlogN$。
对于每次找答案,在线段树中往下走找到那些数值为1的点,同时把值赋成无穷大,以后不再访问这个点,在往上回溯的时候在那些只有一个线段覆盖的区间加上这些1的个数。
然后取得值最多的那个线段执行撤销操作。找到最多的区间这一步可以再用一颗线段树维护。
因为记录区间不需要任何顺序,所以用Hash表即可,STL里的unordered_set就能满足。
总的复杂度就成了$Nlog(N+Q)$

#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<unordered_set>
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int maxn = 1e6 + 23;
const int INF = 0x3f3f3f3f;
int n, q;
PII seg[30300];
struct NodeQ {
    int l, r;
    int v;
}trQ[30300 * 4];
void buildQ(int u, int l, int r)
{
    if (l == r) trQ[u] = { l, r, 0 };
    else
    {
        trQ[u] = { l, r, 0 };
        int mid = l + r >> 1;
        buildQ(u << 1, l, mid), buildQ(u << 1 | 1, mid + 1, r);
    }
}
void pushupQ(int u)
{
    trQ[u].v = max(trQ[u << 1].v, trQ[u << 1 | 1].v);
}
void modifyQ(int u, int p, int x)
{
    if (trQ[u].l == trQ[u].r && trQ[u].r == p) trQ[u].v += x;
    else
    {
        int mid = trQ[u].l + trQ[u].r >> 1;
        if (p <= mid) modifyQ(u << 1, p, x);
        else modifyQ(u << 1 | 1, p, x);
        pushupQ(u);
    }
}
int queryQ(int u)
{
    if (trQ[u].l == trQ[u].r) return trQ[u].l;
    else
    {
        int mid = trQ[u].l + trQ[u].r >> 1;
        if (trQ[u << 1].v == trQ[u].v) return queryQ(u << 1);
        else return queryQ(u << 1 | 1);
    }
}


int w[maxn];
unordered_set<int> st[maxn * 4];
struct Node {
    int l, r;
    int val;
    int add;
}tr[maxn * 4];
void pushdown(int u)
{
    if (tr[u].add == 0) return;
    tr[u << 1].val += tr[u].add;
    tr[u << 1].add += tr[u].add;
    tr[u << 1 | 1].val += tr[u].add;
    tr[u << 1 | 1].add += tr[u].add;
    tr[u].add = 0;
}
void pushup(int u)
{
    tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
}
void build(int u, int l, int r)
{
    if (l == r) tr[u] = { l, r, w[l] ? 0 : INF , 0 };
    else
    {
        tr[u] = { l, r, 0, 0 };
        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 v, int i)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].val += v;
        tr[u].add += v;
        if (v > 0) st[u].insert(i);
        else st[u].erase(i);
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) modify(u << 1, l, r, v, i);
        else if (l > mid) modify(u << 1 | 1, l, r, v, i);
        else modify(u << 1, l, r, v, i), modify(u << 1 | 1, l, r, v, i);
        pushup(u);
    }
}
int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].val;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else return min(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }
}
int query(int u)
{
    //cerr << u << tr[u].l << tr[u].r << endl;
    if (tr[u].l == tr[u].r)
    {
        tr[u].val = INF;
        if (st[u].size() == 1)
            modifyQ(1, *st[u].begin(), 1);
        return 1;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        int len = 0;
        if (tr[u << 1].val == 1) len += query(u << 1);
        if (tr[u << 1 | 1].val == 1) len += query(u << 1 | 1);
        if (st[u].size() == 1)
            modifyQ(1, *st[u].begin(), len);
        pushup(u);
        return len;
    }
}
int main()
{
    int T = 0; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++)
    {
        scanf("%d%d", &n, &q);
        buildQ(1, 1, q);
        if(cas != 1)for (int i = 1; i <= q; i++) st[i].clear();
        if(cas != 1) memset(w, 0, sizeof w);
        for (int i = 1; i <= q; i++)
        {
            scanf("%d%d", &seg[i].first, &seg[i].second);
            //modify(1, seg[i].first, seg[i].second, 1, i);
            w[seg[i].first]++; w[seg[i].second + 1]--;
        }
        for (int i = 1; i <= n; i++) w[i] += w[i - 1];
        build(1, 1, n);
        for (int i = 1; i <= q; i++) modify(1, seg[i].first, seg[i].second, 1, i);

        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= q; i++)
        {
            query(1);
            ans = min(ans, trQ[1].v);
            int sid = queryQ(1);
            modify(1, seg[sid].first, seg[sid].second, -1, sid);
            modifyQ(1, sid, -INF);
        }
        printf("Case #%d: %d\n", cas, ans);
    }
}
/*
1
20 5
9 19
2 5
6 6
2 3
8 19

1
20 5
10 19
2 5
6 6
2 3
9 19

3
5 3
1 2
3 4
2 5
30 3
10 11
10 10
11 11
10 4
1 8
4 5
3 6
2 7
*/


活动打卡代码 AcWing 551. 抢票

#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<unordered_set>
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int maxn = 1e6 + 23;
const int INF = 0x3f3f3f3f;
int n, q;
PII seg[30300];
struct NodeQ {
    int l, r;
    int v;
}trQ[30300 * 4];
void buildQ(int u, int l, int r)
{
    if (l == r) trQ[u] = { l, r, 0 };
    else
    {
        trQ[u] = { l, r, 0 };
        int mid = l + r >> 1;
        buildQ(u << 1, l, mid), buildQ(u << 1 | 1, mid + 1, r);
    }
}
void pushupQ(int u)
{
    trQ[u].v = max(trQ[u << 1].v, trQ[u << 1 | 1].v);
}
void modifyQ(int u, int p, int x)
{
    if (trQ[u].l == trQ[u].r && trQ[u].r == p) trQ[u].v += x;
    else
    {
        int mid = trQ[u].l + trQ[u].r >> 1;
        if (p <= mid) modifyQ(u << 1, p, x);
        else modifyQ(u << 1 | 1, p, x);
        pushupQ(u);
    }
}
int queryQ(int u)
{
    if (trQ[u].l == trQ[u].r) return trQ[u].l;
    else
    {
        int mid = trQ[u].l + trQ[u].r >> 1;
        if (trQ[u << 1].v == trQ[u].v) return queryQ(u << 1);
        else return queryQ(u << 1 | 1);
    }
}


int w[maxn];
unordered_set<int> st[maxn * 4];
struct Node {
    int l, r;
    int val;
    int add;
}tr[maxn * 4];
void pushdown(int u)
{
    if (tr[u].add == 0) return;
    tr[u << 1].val += tr[u].add;
    tr[u << 1].add += tr[u].add;
    tr[u << 1 | 1].val += tr[u].add;
    tr[u << 1 | 1].add += tr[u].add;
    tr[u].add = 0;
}
void pushup(int u)
{
    tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
}
void build(int u, int l, int r)
{
    if (l == r) tr[u] = { l, r, w[l] ? 0 : INF , 0 };
    else
    {
        tr[u] = { l, r, 0, 0 };
        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 v, int i)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].val += v;
        tr[u].add += v;
        if (v > 0) st[u].insert(i);
        else st[u].erase(i);
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) modify(u << 1, l, r, v, i);
        else if (l > mid) modify(u << 1 | 1, l, r, v, i);
        else modify(u << 1, l, r, v, i), modify(u << 1 | 1, l, r, v, i);
        pushup(u);
    }
}
int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].val;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else return min(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }
}
int query(int u)
{
    //cerr << u << tr[u].l << tr[u].r << endl;
    if (tr[u].l == tr[u].r)
    {
        tr[u].val = INF;
        if (st[u].size() == 1)
            modifyQ(1, *st[u].begin(), 1);
        return 1;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        int len = 0;
        if (tr[u << 1].val == 1) len += query(u << 1);
        if (tr[u << 1 | 1].val == 1) len += query(u << 1 | 1);
        if (st[u].size() == 1)
            modifyQ(1, *st[u].begin(), len);
        pushup(u);
        return len;
    }
}
int main()
{
    int T = 0; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++)
    {
        scanf("%d%d", &n, &q);
        buildQ(1, 1, q);
        if(cas != 1)for (int i = 1; i <= q; i++) st[i].clear();
        if(cas != 1) memset(w, 0, sizeof w);
        for (int i = 1; i <= q; i++)
        {
            scanf("%d%d", &seg[i].first, &seg[i].second);
            //modify(1, seg[i].first, seg[i].second, 1, i);
            w[seg[i].first]++; w[seg[i].second + 1]--;
        }
        for (int i = 1; i <= n; i++) w[i] += w[i - 1];
        build(1, 1, n);
        for (int i = 1; i <= q; i++) modify(1, seg[i].first, seg[i].second, 1, i);

        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= q; i++)
        {
            query(1);
            ans = min(ans, trQ[1].v);
            int sid = queryQ(1);
            modify(1, seg[sid].first, seg[sid].second, -1, sid);
            modifyQ(1, sid, -INF);
        }
        printf("Case #%d: %d\n", cas, ans);
    }
}
/*
1
20 5
9 19
2 5
6 6
2 3
8 19

1
20 5
10 19
2 5
6 6
2 3
9 19

3
5 3
1 2
3 4
2 5
30 3
10 11
10 10
11 11
10 4
1 8
4 5
3 6
2 7
*/


活动打卡代码 AcWing 255. 第K小数

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 23;
int n, m, a[maxn], ra[maxn];
set<int> st;
unordered_map<int,int> ump;
struct Node{
    int l, r, cnt;
}tr[maxn * 20];
int root[maxn], idx;
int build(int l, int r)
{
    int p = ++idx;
    if(l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid);
    tr[p].r = build(mid + 1, r);
    return p;
}
void pushup(Node &u, Node &l, Node &r)
{
    u.cnt = l.cnt + r.cnt;
}
int insert(int p, int l, int r, int x)
{
    int q = ++idx;
    tr[q] = tr[p];
    if(l == r) 
    {
        tr[q].cnt++;
        return q;
    }
    int mid = l + r >> 1;
    if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    if(x > mid) tr[q].r = insert(tr[p].r, mid + 1, r, x);
    pushup(tr[q], tr[tr[q].l], tr[tr[q].r]);
    return q;
}
int query(int p, int q, int l, int r, int k)
{
    if(l == r) return l;
    int mid = l + r >> 1;
    int v = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    if(v >= k) return query(tr[p].l, tr[q].l, l, mid, k);
    else return query(tr[p].r, tr[q].r, mid + 1, r, k - v);
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) 
    {
        scanf("%d", &a[i]);
        st.insert(a[i]);
    }
    int sz = 0;
    for(auto it = st.begin(); it != st.end(); it++)
    {
        ump[*it] = ++sz;
        ra[sz] = *it;
    }
    root[0] = build(1, sz);
    for(int i = 1; i <= n; i++)
    {
        root[i] = insert(root[i - 1], 1, sz, ump[a[i]]);
    }
    for(int i = 1; i <= m; i++)
    {
        int l = 0, r = 0, k = 0;
        scanf("%d%d%d", &l, &r, &k);
        int ans = query(root[l - 1], root[r], 1, sz, k);
        printf("%d\n", ra[ans]);
    }
}


活动打卡代码 AcWing 256. 最大异或和

#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e5;
int tr[maxn * 25][2], max_id[maxn * 25];
int a[maxn], root[maxn];
int n, m, idx;
void insert(int i, int k, int p, int q)
{
    //cerr << k << endl;
    if(k < 0)
    {
        max_id[q] = i;
        return;
    }
    int v = a[i] >> k & 1;
    if(p) tr[q][v ^ 1] = tr[p][v ^ 1];
    tr[q][v] = ++idx;
    insert(i, k - 1, tr[p][v], tr[q][v]);
    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}
int query(int p, int c, int L)
{
    for(int i = 23; i >= 0; i--)
    {
        int v = c >> i & 1;
        if(tr[p][v ^ 1] && max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
        else p = tr[p][v];
    }
    return c ^ a[max_id[p]];
}
int main()
{
    scanf("%d%d", &n, &m);
    max_id[0] = -1;
    root[0] = ++idx;
    insert(0, 23, 0, root[0]);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        a[i] ^= a[i - 1];
        root[i] = ++idx;
        insert(i, 23, root[i - 1], root[i]);
    }
    char op[2];
    int l = 0, r = 0, x = 0;
    for(int i = 1; i <= m; i++)
    {
        scanf("%s", op);
        if(*op == 'A')
        {
            //cerr << "in" << endl;
            scanf("%d", &a[++n]);
            a[n] ^= a[n - 1];
            root[n] = ++idx;
            insert(n, 23, root[n - 1], root[n]);
        }
        else 
        {
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(root[r - 1], a[n] ^ x, l - 1));
        }
    }
}


活动打卡代码 AcWing 1277. 维护序列

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 23;
int a[maxn];
int n, p;
struct Node{
    int l, r;
    ll sum, mul, add;
    // sum = sum * mul + add
}tr[maxn * 4];

void pushup(Node &u, Node &l, Node &r)
{
    u.sum = (l.sum + r.sum) % p;
}
void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if(l == r) tr[u] = { l, r, a[l], 1, 0};
    else 
    {
        tr[u] = {l, r, 0, 1, 0};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void pushdown(Node &u, Node &l, Node &r)
{
    l.sum = (l.sum * u.mul + (l.r - l.l  + 1) * u.add) % p;
    l.mul = l.mul * u.mul % p; 
    l.add = (l.add * u.mul + u.add) % p;
    r.sum = (r.sum * u.mul + (r.r - r.l + 1) * u.add) % p;
    r.mul = r.mul * u.mul % p; 
    r.add = (r.add * u.mul + u.add) % p;
    u.mul = 1; u.add = 0;
}
void pushdown(int u)
{
    pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
ll query(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;
        if(r <= mid) return query(u << 1, l, r);
        if(l > mid) return query(u << 1 | 1, l, r);
        return query(u << 1, l, r) + query(u << 1 | 1, l, r);
    }
}
void modify(int u, int l, int r, int mul, int add)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum = (tr[u].sum * mul + (tr[u].r - tr[u].l + 1) * add) % p;
        tr[u].mul = (tr[u].mul * mul) % p; 
        tr[u].add = (tr[u].add * mul + add) % p;
    }
    else 
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) modify(u << 1, l, r, mul, add);
        else if(l > mid) modify(u << 1 | 1, l, r, mul, add);
        else modify(u << 1, l, r, mul, add), modify(u << 1 | 1, l, r, mul, add);
        pushup(u);
    }
}
int main()
{
    scanf("%d%d", &n, &p);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1,1,n);
    int op = 0, t = 0, g = 0, c = 0;
    int m = 0; scanf("%d", &m);
    while(m--)
    {
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d%d%d", &t, &g, &c);
            modify(1, t, g, c, 0);
        }
        if(op == 2)
        {
            scanf("%d%d%d", &t, &g, &c);
            modify(1, t, g, 1, c);
        }
        if(op == 3)
        {
            scanf("%d%d", &t, &g);
            printf("%lld\n", query(1, t, g) % p);
        }
    }


}



#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 23;
struct Node{
    int l, r;
    ll v, d;
}tr[maxn * 4];
ll a[maxn], b[maxn];
void pushup(Node &u, Node &l, Node &r)
{
    u.v = l.v + r.v;
    u.d = __gcd(l.d, r.d);
}
void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
    //printf("%d[%d,%d]=%d\n",u,tr[u].l,tr[u].r,tr[u].d);
}
void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, b[l], b[l]};
    else 
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
ll query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].d;
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);
        else return __gcd(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }
}
ll query2(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query2(u << 1, l, r);
        else if(l > mid) return query2(u << 1 | 1, l, r);
        else return query2(u << 1, l, r) + query2(u << 1 | 1, l, r);
    }
}
void modify(int u, int p, ll v)
{
    if(tr[u].l == tr[u].r && tr[u].l == p) tr[u].d += v, tr[u].v += v;
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(p <= mid) modify(u << 1, p, v);
        else modify(u << 1 | 1, p, v);
        pushup(u);
    }
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i] - a[i - 1];
    build(1, 1, n);
    char op[4];
    ll op1 = 0, op2 = 0, op3 = 0;
    while(m--)
    {
        scanf("%s%lld%lld", op, &op1, &op2);
        if(*op == 'C') 
        {
            scanf("%lld", &op3);
            modify(1, op1, op3);
            if(op2 + 1 <= n) modify(1, op2 + 1, -op3);
        }
        else 
        {
            ll t = query2(1, 1, op1); //cout << t << endl;
            printf("%lld\n", abs( __gcd(t, query(1, op1 + 1, op2))));
        }
    }
}

/*
1 2 2 2 2 / 1 3 5 7 9
2 2 2 2 2 / 2 4 6 8 10
2 2 8 -4 2 / 2 4 12 8 10
*/



#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 23;
struct Node{
    int l, r;
    int sum, lmax, rmax, smax;
}tr[maxn * 4];
int a[maxn];
void pushup(Node &u, Node &l, Node &r)
{
    u.sum = l.sum + r.sum;
    u.lmax = max(r.lmax + l.sum, l.lmax);
    u.rmax = max(l.rmax + r.sum, r.rmax);
    u.smax = max(max(l.smax, r.smax), l.rmax + r.lmax);
}
void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, a[l], a[l], a[l], a[l]};
    else 
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int p, int v)
{
    if(tr[u].l == tr[u].r && tr[u].l == p) tr[u] = {p, p, v, v, v, v};
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(p <= mid) modify(u << 1, p, v);
        else modify(u << 1 | 1, p, v);
        pushup(u);
    }
}
Node query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l ,r);
        else 
        {
            Node leftv = query(u << 1, l, r), rightv = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, leftv, rightv);
            return res;
        }
    }
}
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    int x = 0, y = 0, op = 0;
    while(m--)
    {
        scanf("%d%d%d", &op, &x, &y);

        if(op == 1) 
        {
            if(x > y) swap(x, y);
            printf("%d\n", query(1, x, y).smax);
        }
        else modify(1, x, y);
    }
}


活动打卡代码 AcWing 1086. 恨7不成妻

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 1e9 + 7;
struct F{
    ll s0, s1, s2;
}f[20][10][7][7];
//整数的每一位加起来的和是 7 的整数倍;
//这个整数是 7 的整数倍。
F gao(int i, int j, ll a, ll b)
{
    a = (a % 7 + 7) % 7;
    b = (b % 7 + 7) % 7;
    ll ret0 = 0, ret1 = 0, ret2 = 0;
    for(int x = 0; x < 7; x++)
        for(int y = 0; y < 7; y++)
            if(x != a && y != b)
            {
                auto &t = f[i][j][x][y];
                ret0 += t.s0; ret0 %= p;
                ret1 += t.s1; ret1 %= p;
                ret2 += t.s2; ret2 %= p;
            }
    return {ret0, ret1, ret2};
}
ll powerp[20], power7[20];
ll dp(ll x)
{
    ll back = x % p;
    vector<int> v;
    while(x) v.push_back(x % 10), x /= 10;
    ll res = 0, lasta = 0, lastb = 0;
    for(int i = v.size() - 1; i >= 0; i--)
    {
        x = v[i];
        for(int j = 0; j < x; j++)
        {
            //cout << j << endl;
            if(j == 7) continue;
            auto t = gao(i + 1, j, -lasta, -lastb * power7[i + 1]);
            res += lastb % p * (lastb % p) % p * powerp[i + 1] % p * powerp[i + 1] % p * t.s0 % p 
                    + 2 * (lastb % p) % p * powerp[i + 1] % p * (t.s1 % p) % p + t.s2 % p;
            res %= p;
            //
        }
        //cout << res << endl;
        if(x == 7) break;
        lasta += x;
        lastb = lastb * 10 + x;
        if(!i && lasta % 7 && lastb % 7) res = (res + back * back) % p;
    }
    return res % p;
}
int main()
{
    for(int i = 0; i < 10; i++) 
    {
        if(i == 7) continue;
        auto &t = f[1][i][i % 7][i % 7];
        t.s0++, t.s1 += i, t.s2 += i * i;
    }
    powerp[0] = 1; power7[0] = 1; 
    ll po = 10; powerp[1] = po; power7[1] = 10 % 7;
    for(int i = 2; i < 20; i++, po *= 10LL)
    {
        powerp[i] = powerp[i - 1] * 10 % p; power7[i] = power7[i - 1] * 10 % 7;
        for(int j = 0; j < 10; j++)
        {
            if(j == 7) continue;
            for(int a = 0; a < 7; a ++)
                for(int b = 0; b < 7; b++)
                {
                    for(int k = 0; k < 10; k++)
                    {
    if(k == 7) continue;
    auto &s = f[i - 1][k][a][b], &d = f[i][j][(a + j) % 7][(b + j * po) % 7];
    //auto &s = f[i - 1][k][((a - j) % 7 + 7) % 7][((b - j * po) % 7 + 7) % 7], &d = f[i][j][a][b];
    d.s0 += s.s0; d.s0 %= p;
    d.s1 += po % p * j % p * s.s0 % p + s.s1 % p; d.s1 %= p;
    d.s2 += po % p * j % p * j % p * (po % p) % p * s.s0 % p + 2 * j * (po % p) % p * s.s1 % p + s.s2 % p; d.s2 %= p;
                    }
                }

        }
    }
    //  for(int i = 1; i <= 5; i++)
    //      for(int j = 0; j < 10; j++) 
    //          cout << f[i][j][4][3].s2 << endl;
    //cout << dp(2065) << endl;
    int T; cin >> T;
    while(T--)
    {
        ll l, r; cin >> l >> r;
        cout << ((dp(r) - dp(l - 1)) % p + p) % p << endl;
    }
}


活动打卡代码 AcWing 1085. 不要62

#include<bits/stdc++.h>
using namespace std;
int f[15][15];
int dp(int x)
{
    if(x == 0) return 1;

    vector<int> v;
    while(x) v.push_back(x % 10), x /= 10;
    int res = 0, last = 0, flag = 0, flag2 = 0;
    for(int i = v.size() - 1; i >= 0; i--)
    {
        x = v[i];
        for(int j = 0; j < x; j++)
        {
            if(j == 4) continue;
            if(j == 2 && last == 6) continue;
            else res += f[i + 1][j];
        }
        if(x == 2 && last == 6) break;
        if(x == 4) break;
        last = x;
        if(!i) res++;
    }
    //if(!flag && !flag2) res++;
    return res;
}
int main()
{
    for(int i = 0; i < 10; i++) f[1][i] = 1; f[1][4] = 0;
    for(int i = 2; i <= 11; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            if(j == 4) continue;
            for(int k = 0; k < 10; k++)
            {
                if(j == 6 && k == 2) continue;
                if(k == 4) continue;
                f[i][j] += f[i - 1][k];
            }
        }
    }
    int l, r;
    while(cin >> l >> r)
    {
        if(l == 0 && r == 0) return 0;
        cout << dp(r) - dp(l - 1) << endl;
    }
}


活动打卡代码 AcWing 1084. 数字游戏 II

#include<bits/stdc++.h>
using namespace std;
long long f[15][101];
int n;
int dp(int x)
{
    if(x == 0) return 1;
    vector<int> v;
    while(x) v.push_back(x % 10), x /= 10;
    int res = 0, last = 0;
    for(int i = v.size() - 1; i >= 0; i--)
    {
        x = v[i];
        for(int j = 0; j < x; j++)
        {
            if(!i)
            {
                if((last + j) % n == 0) res++;
            }
            else
            {
                int t = n - last - j; t %= n; t += n; t %= n;
                res += f[i][t];
            }
        }
        last += x; last %= n;
        if(!i && !last) res ++;
    }
    return res;
}
int main()
{
    int a, b;
    while(cin >> a >> b >> n)
    {
        memset(f, 0, sizeof f);
        //for(int i = 0; i < n; i++) f[0][i] = 1;
        for(int i = 0; i < 10; i++) f[1][i % n]++;
        for(int i = 2; i <= 11; i++)
        {
            for(int j = 0; j <= 9; j++)
                for(int k = 0; k < n; k++)
                {
                    f[i][(j + k) % n] += f[i - 1][k];
                }
        }

        //cout << dp(0) << endl;
        cout << dp(b) - dp(a - 1) << endl;
    }
}