「题单」IOI2020国家集训队作业 Part 1

📅 Last Updated: 2020-10-19

📊 Word Count: 836

⏱️ Estimated Reading Time: 6 minutes

📄 PDF 📝 Source

CF505E Mr. Kitayuta vs. Bamboos

给定 $n$ 个数（竹子的高度） $h_{1 \dots n}$ 。
你需要进行 $m$ 轮操作，每轮操作为 $k$ 次修改，每次修改可以选择一个数 $h_i$ 修改为 $\max(h_i - p, 0)$ （砸到地下）。
每轮操作后每个 $h_i$ 将会被修改为 $h_i + a_i$ （每天竹子会生长）。
你需要最小化最终 $h_{1 \dots n}$ 中的最大值。
$n \le 10^5$ ， $m \le 5 \times 10^3$ ， $k \le 10$ 要求最小化最大值，考虑二分一个最大的高度，将问题转化成可行性问题，即，给出一个高度，问能否使这些竹子最终不超过这个高度。

考虑限制这个问题不平凡的因素：因为每次降低竹子高度的时候不能保证竹子一定降低 p ，也就是说，“砸竹子”这一动作存在浪费。我们考虑尽可能的让“砸竹子”这一动作更少的浪费，即：尽可能在后面的时间点砸竹子，但是无法保证到底是在哪一次砸竹子，有可能已经结束了，没有形式化的计算流程。

可以考虑反向思考，即：假设已经长到二分的高度。每次生长操作相当于每次会下落 $a_i$ ，而每次砸的操作相当于提升了 $p$ 的高度。

开始时，对每一个竹子计算出其需要多少次会下落到负高度，用堆维护，每次取出最快的可能下落到负高度的 k 个竹子，进行 “拔高” 操作。然后判断最后的高度是否大于等于 $h_i$ 。

其实二分的本质是为了确定“尽可能的靠后砸竹子”的标准。反向思考是为了便于贪心处理策略。 ## code

int n, m, k, p;
int H[_], A[_];
#define mp make_pair
#define fi first
#define se second
int height[_];
bool check(int MaxH){
    fill(height + 1, height + 1 + n, MaxH);
    priority_queue<pair<int, int>, vector<pair<int, int> > , greater<pair<int, int> > > Q;
    while(!Q.empty()) Q.pop();
    for(int i = 1; i <= n; i++) if(MaxH - m * A[i] < H[i]) Q.push(mp( MaxH / A[i], i ));

    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= k; j++){
            if(Q.empty()) return true;
            pair<int, int> now = Q.top(); Q.pop(); 
            if(now.fi < i) return false;
            height[now.se] += p;
            now.fi = height[now.se] / A[now.se];
            if(height[now.se] - m * A[now.se] < H[now.se]) Q.push(now);
        }
    }
    return Q.empty();
}
signed main(){
    n = read(), m = read(), k = read(), p = read(); // 竹子数 天数 修改次数 最大降低高度 
    for(int i = 1; i <= n; i++) H[i] = read(), A[i] = read();

    int L = 0, ans = 0, R = 1LL << 60; for(int i = 1; i <= n; i++) L = min(L, A[i]);
    while(L < R){
        int mid = (L + R) >> 1;
        if(check(mid)) ans = mid, R = mid;
        else L = mid + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

CF521D Shop

有 $k$ 个正整数 $a_{1\dots k}$ 。
有 $n$ 个操作，每个操作给定正整数 $b$ ，有三种可能：将 $a_i$ 赋值为 $b$ ，将 $a_i$ 加上 $b$ ，将 $a_i$ 乘以 $b$ 。
你可以从 $n$ 个操作中选择最多 $m$ 个操作，并按照一定顺序执行。
你的目标是最大化 $\prod_{i=1}^k a_i$ 的值。
$k,n \le 10^5$ 。

化归思想，考虑如果只有乘法，那一定是把操作数字从大到小排序，然后以此操作。

考虑操作顺序，最优的操作一定是先赋值，再加法，最后乘法。其中赋值只可能选相应位置最大的赋值，加法也是从大到小考虑。

显然赋值可以直接转化成加法，而加法如果从大到小考虑也可以直接转化成乘法（乘一个实数）。

这样就把所有操作转化成了乘法。贪心考虑即可。

最后输出有顺序，应按照上面的策略（先赋值，再加法，最后乘法）以此输出（操作顺序）。

code

#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int _ = 1e5 + 100;
#define LL long long
int read() { int x; scanf("%d", &x); return x; }
int n, m, k;
int v[_];
pair<int, int> Give[_];
vector<pair<int, int > > add[_];
vector<pair<double, int> > mul[_];
vector<pair<double, int> > All;
int T[_];
int id[_];
#define double long double
bool ICMP  (const pair<int, int> & x, const pair<int, int> & y) { return (x > y); }
bool ICMP_D(const pair<double, int> & x, const pair<double, int> & y) { return (x > y); }
bool MAGIC(const int &x, const int &y) { return T[x] < T[y]; }
int main(){
    k = read(), n = read(), m = read();
    for(int i = 1; i <= k; i++) v[i] = read();

    for(int i = 1; i <= n; i++){
        int type = read(); T[i] = type;
        int a = read(), b = read();
        if(type == 1){
            Give[a] = max(Give[a], make_pair(b, i)); 
        } else if(type == 2){
            add[a].push_back(make_pair(b, i));
        } else {
            mul[a].push_back(make_pair((double)(b), i));
        }
    }
    for(int i = 1; i <= k; i++)
        if(Give[i].first)
            add[i].push_back(make_pair(Give[i].first - v[i], Give[i].second));
    for(int i = 1; i <= k; i++) sort(add[i].begin(), add[i].end(), ICMP);
    for(int i = 1; i <= k; i++){
        LL now = v[i];
        for(int j = 0; j < add[i].size(); j++){
            mul[i].push_back( 
                make_pair( 
                    (double)(now +0ll+ add[i][j].first) / (double)(now),
                    add[i][j].second
                ) 
            ); now += add[i][j].first;
        }
    }
    for(int i = 1; i <= k; i++) for(int j = 0; j < mul[i].size(); j++) All.push_back(mul[i][j]);
    sort(All.begin(), All.end(), ICMP_D);
    int tot = 0;
    for(int i = 0; i < All.size(); i++) if(All[i].first > 1) { tot++; }
    tot = min(tot, m);
    for(int i = 1; i <= tot; i++) id[i] = All[i - 1].second;
    sort(id + 1, id + 1 + tot, MAGIC);  printf("%d\n", tot);
    for(int i = 1; i <= tot; i++) printf("%d%c", id[i], " \n"[i == n]);
    return 0;
}

CF526F Pudding Monsters

给定一个 $n \times n$ 的棋盘，其中有 $n$ 个棋子，每行每列恰好有一个棋子。
求有多少个 $k \times k$ 的子棋盘中恰好有 $k$ 个棋子。
$n \le 3 \times 10^5$ 。

每行每列恰好有一个棋子的棋盘，可以抽象成一个排列。而操作也是对于一个排列的一段进行操作的。

题意可以转化为： - 给出一个排列 - 求连续段数量，即连续的一段，且段中的元素排好序之后必须是公差为 $1$ 的等差数列.

连续段计数

考虑如何刻画“连续的一段，且段中的元素排好序之后必须是公差为 $1$ 的等差数列”这个条件，可以形式化的定义：

$\operatorname{MaxVal} - \operatorname{MinVal} = (R - L)$

即

$f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) = 0$

这个条件成立的基础在于，所求数列不能有重复元素，而且也保证了函数 $f_x(L) \ge 0$ , 查询时只需要维护最小值以及最小值的数量即可。

可以考虑枚举一个端点，比如右端点 $R$ ，然后查找有多少符合条件的左端点 $L$ ，用线段树维护 $f_R(x)$ 在每个点处的函数值。

考虑当 $f_x(L)$ 移动到 $f_{x + 1}(L)$ 时，值的变化。变化的值有 $R$ , 可能变化的有 $MaxVal, MinVal$ 。用单调栈实时维护更新后会波及哪些元素的最小值。事实上，单调栈处理的过程就是在动态维护一个后缀最小/大值数组。

这里有几个与其有相似之处的题目，但是可能做法并不一样，遇到不要想成一样的题目： - 算术天才⑨与等差数列 (不保证序列中一定元素不重复) - 考虑判断一个序列排好序后是否为等差数列 - 准确做法 - $\max−\min=(r−l)k$ - 相邻两数差的绝对值的 $\operatorname{gcd}$ 是 $k$ - 区间 $[l,r]$ 内的数不重复 - 概率性做法 - hash思想，维护 $n$ 次方和 - 树上排列(ZROI) (同样不保证元素一定不重复) - 给定一颗 $n$ 个点的树。每个点都一个正整数点权 $A_i$ ，你需要支持以下两种操作： - 1、询问点 $x$ 和点 $y$ 之间的路径上的所有点（包括点 $x$ 和点 $y$ ）的点权是否构成一个从 $1$ 开始的排列（即若这条链长度为 $len$ ，那么问点权集合为 ${1,2,⋯,len}$ ）。 - 2、将 $A_x$ 修改为 $y$ 。 - 由于在树上难以判断某区间内的数字不重复，Hash维护n次方和。 - 给出一个没有重复元素的序列，询问某区间中的元素是否能加入小于 $k$ 个元素使其拍好序后构成一个等差数列。 - 条件变成了 $f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) \ge k$ - count(ZROI)已知一个集合 $S$ 中的最大元素为 $N$ ，且这个集合中的元素可以构成一个等差数列，给出一些形如 $x \in S$ 、 $x \notin S$ 的限制。求最终的集合有多少种情况。 - 考虑刻画一个等差数列需要什么参数：公差，和每个元素 $\bmod$ 公差的值。枚举这两个参数，依次计数即可。

（引用正睿的两道题目，不知道是不是有版权问题，如果有，会立即删除（~~顺便给正睿OI打个广告~~））。

code

int n;
int A[_];
#define fir first
#define sec second
namespace SegmentTree{
    const int _ = 3e6 + 100;
    struct Node{
        int MIN;
        int sMIN;
        int tar;
        Node operator + (const Node & rhs) const {
            Node res;
            res.MIN  = min(MIN, rhs.MIN);
            res.sMIN = MIN == rhs.MIN ? ( sMIN + rhs.sMIN) : (MIN < rhs.MIN ? sMIN : rhs.sMIN) ;
            return res;
        }
    }v[_];
    int tot = 0;
    int ch[_][2];
    #define ls(o) (ch[o][0])
    #define rs(o) (ch[o][1])
    #define make (tot++, ch[tot][0] = ch[tot][1] = v[tot].MIN = v[tot].sMIN = 0, tot)
    int Groot() { return make; }
    void maintain(int o) {
        v[o].MIN  = min(v[ls(o)].MIN, v[rs(o)].MIN);
        v[o].sMIN = v[ls(o)].MIN == v[rs(o)].MIN ? v[ls(o)].sMIN + v[rs(o)].sMIN : ( v[ls(o)].MIN < v[rs(o)].MIN ? v[ls(o)].sMIN : v[rs(o)].sMIN );
    }
    void tar(int o, int x) { v[o].MIN += x; v[o].tar += x; }
    void pushdown(int o){
        if(v[o].tar){
            tar(ls(o), v[o].tar); tar(rs(o), v[o].tar);
            v[o].tar = 0;
        }
    }
    void build(int o, int L, int R){
        if(L == R) { v[o].MIN = 0; v[o].sMIN = 1; return; }
        int mid = (L + R) >> 1;
        ls(o) = make; rs(o) = make;
        build(ls(o), L, mid); build(rs(o), mid + 1, R);
        maintain(o);
    }
    void update(int o, int nowl, int nowr, int L, int R, int x){
        if(L > R) return ;
        if(L <= nowl && nowr <= R) return tar(o, x);
        int mid = (nowl + nowr) >> 1;  pushdown(o);
        if(L <= mid) update(ls(o), nowl, mid, L, R, x);
        if(R  > mid) update(rs(o), mid + 1, nowr, L, R, x);
        maintain(o);
    }
    Node query(int o, int nowl, int nowr, int L, int R) {
        if(L <= nowl && nowr <= R) return v[o];
        int mid = (nowl + nowr) >> 1; pushdown(o);
        Node Ans; Ans.MIN = INT_MAX;
        if(L <= mid) Ans = Ans + query(ls(o), nowl, mid, L, R);
        if(R  > mid) Ans = Ans + query(rs(o), mid + 1, nowr, L, R);
        return Ans;
    }
    int query(int o, int L, int R){
        Node res = query(o, 1, n, L, R);
        return res.MIN == 0 ? res.sMIN : 0;
    }
}  using SegmentTree::Groot; using SegmentTree::build; using SegmentTree::query; using SegmentTree::update;
namespace Mon_Stack{
    int t0t = 0, t1t = 0;
    pair<int, int> S0[_], S1[_];
    int work(int *A, int n){
        int Ans = 0;
        int root = Groot();
        build(root, 1, n);
        S0[0].fir = S1[0].fir = 0;
        for(int i = 1; i <= n; i++) {
            update(root, 1, n, 1, i - 1, -1);
            while(t0t != 0 && S0[t0t].sec >= A[i]) { update(root, 1, n, S0[t0t - 1].fir + 1, S0[t0t].fir,  S0[t0t].sec); t0t--; }
            while(t1t != 0 && S1[t1t].sec <= A[i]) { update(root, 1, n, S1[t1t - 1].fir + 1, S1[t1t].fir, -S1[t1t].sec); t1t--; }
            update(root, 1, n, S0[t0t].fir + 1, i, -A[i]);
            update(root, 1, n, S1[t1t].fir + 1, i, A[i]);
            int t = query(root, 1, i);
            Ans += t;
            S0[++t0t] = make_pair(i, A[i]); S1[++t1t] = make_pair(i, A[i]);
        }
        return Ans;
    }
} using Mon_Stack::work;
signed main(){
    n = read(); for(int i = 1; i <= n; i++) { int x = read(), y = read(); A[x] = y; }
    printf("%lld\n", work(A, n));
    return 0;
}

#include <climits>
#include <cmath>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long 
const int MOD = 1e9 + 7;
const int _M = 2e5 + 100;
inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; }
int MAX, m;
int have[_M], tht = 0;
int none[_M], tnt = 0;
int d[_M], tdt = 0; 
int c[_M];//tct = tdt
bool CanBe[_M];
int ToL[_M];
int ToR[_M];
void divide(int s, int x) {
    for(int i = 1; i * i <= x; i++){
        if(x % i == 0) d[++tdt] = i, c[tdt] = s % i;
        if(i * i != x) d[++tdt] = x / i, c[tdt] = s % d[tdt];
    }
    for(int i = 1; i <= tdt; i++) CanBe[i] = true;
}
signed main(){
    int t;
    MAX = read(), m = read();
    for(int i = 1; i <= m; i++){
        int type = read();
        if(type == 1) have[++tht] = read();
        else          none[++tnt] = read();
    }
    sort(have + 1, have + 1 + tht); sort(none + 1, none + 1 + tnt);
    int maxd = INT_MAX, Sta;
    for(int i = 2; i <= tht; i++) {
        if(maxd > have[i] - have[i - 1]){
            maxd = have[i] - have[i - 1];
            Sta = have[i - 1];
        }
    }
    divide(Sta, maxd);

    /* 公差 及 特征 检查   */
    for(int i = 1; i <= tht; i++){
        for(int j = 1; j <= tdt; j++){
            if(!CanBe[j]) continue;
            if(have[i] % d[j] != c[j]) CanBe[j] = false;
        }
    }
    for(int i = 2; i <= tht; i++){
        int D = have[i] - have[i - 1];
        for(int j = 1; j <= tdt; j++){
            if(!CanBe[j]) continue;
            if(D % d[j] != 0) CanBe[j] = false;
        }
    }
    t = 0;
    for(int i = 1; i <= tdt; i++){
        if(!CanBe[i]) continue;
        d[++t] = d[i];
        c[  t] = c[i];
        CanBe[t] = true;
    } tdt = t;
    /* 公差 及 特征 检查   完成*/
    for(int i = 1; i <= tdt; i++) { 
        if(CanBe[i]) {
            ToL[i] = (c[i] == 0 ? d[i] : c[i]) - 1;
            int t = MAX % d[i];
            if(t == c[i]) ToR[i] = MAX + 1;
            if(t  > c[i]) ToR[i] = MAX - (t - c[i]) + 1;
            if(t  < c[i]) ToR[i] = MAX - d[i] + (c[i] - t) + 1;
        }
    }
    t = 0;
    for(int i = 1; i <= tdt; i++){
        if(!CanBe[i]) continue;
        d[++t] = d[i];
        c[  t] = c[i];
        CanBe[t] = true;
    } tdt = t;
    int MINS = have[1], MAXE = have[tht];
    for(int i = 1; i <= tnt; i++){
        int now = none[i];
        for(int j = 1; j <= tdt; j++){
            if(!CanBe[j]) continue;
            if(now % d[j] == c[j]){
                if(now < MINS)
                    ToL[j] = max(ToL[j], now);
                else if(now > MAXE)
                    ToR[j] = min(ToR[j], now);
                else CanBe[j] = false;
            }
        }
    }
    for(int i = 1; i <= tdt; i++) if(ToL[i] > MINS || ToR[i] < MAXE) CanBe[i] = false; else ToL[i]++, ToR[i] --;
    /* 非法数字存在性检查 */
    int ans = 0;
    for(int i = 1; i <= tdt; i++){
        if(!CanBe[i]) continue;
        int k = (  (MINS - ToL[i]) / d[i] + 1) * ( (ToR[i] - MAXE) / d[i] + 1) % MOD; // TODO;
        ans = (ans + k) % MOD;
    }
    printf("%lld", ans);
    return 0;
}

#include <climits> 
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; }
using namespace std;
const int _ = 6e5 + 100;
const int base = 15;
const int MOD = 1020031005;
int SS[_];
int pow(int a, int b = base){ int ans = 1; while(b){ if(b & 1) ans = (ans *1ll* a) % MOD; a = (a *1ll* a) % MOD; b >>= 1; } return ans; }

int head[_];
int NodeVal[_];
struct edges{
    int node;
    int nxt;
}edge[_];
int tot = 0;
void add(int u, int v){
    tot++;
    edge[tot].node = v;
    edge[tot].nxt  = head[u];
    head[u]        = tot;
}

int n, q;
int dep[_], fa[_], dfn[_], rnk[_], top[_], son[_], si[_], dfc = 0;
void dfs0(int now, int f, int dp){
    int &S = si[now] = 1; int &Mid = son[now] = 0; fa[now] = f; dep[now] = dp;
    for(int i = head[now]; i ; i = edge[i].nxt){
        int ex = edge[i].node; if(ex == f) continue;
        dfs0(ex, now, dp + 1); S += si[ex];
        if(si[ex] > si[Mid]) Mid = ex;
    } if(!Mid) Mid = 0;
}
void dfs1(int now, int f, int tp){
    dfn[now] = ++dfc; rnk[dfc] = now;
    top[now] = tp;
    if(son[now]) dfs1(son[now], now, tp);
    for(int i = head[now]; i ; i = edge[i].nxt){
        int ex = edge[i].node; if(ex == f || ex == son[now]) continue;
        dfs1(ex, now, ex);
    }
}
void clear(){
    memset(head, 0, sizeof(head));
    dfn[0] = rnk[0] = si[0] = top[0] = fa[0] = son[0] = 0;
    tot = 0;
    dfc = 0; 
}
namespace SegmentTree{
    const int _ = 3e6 + 100;
    int tot = 0;
    int ch[_][2];
    int v[_];
    #define make (tot++, ch[tot][0] = ch[tot][1] = v[tot] = 0, tot);
    #define ls(x) (ch[x][0])
    #define rs(x) (ch[x][1])
    #define maintain(o) (v[o] = (v[ls(o)] +0ll+ v[rs(o)]) % MOD )
    void init_s() { tot = 0; }
    int  Groot(){ return make; }
    void build(int o, int L, int R){
        if(L == R) return (void)(v[o] = pow(NodeVal[rnk[L]]));
        int mid = (L + R) >> 1;
        ls(o) = make; rs(o) = make;
        build(ls(o), L, mid); build(rs(o), mid + 1, R);
        maintain(o);
    }
    void update(int o, int nowl, int nowr, int p, int x){
        if(nowl == nowr) return (void)(v[o] = pow(x));
        int mid = (nowl + nowr) >> 1;
        if(p <= mid) update(ls(o), nowl, mid, p, x);
        if(p  > mid) update(rs(o), mid + 1, nowr, p, x);
        maintain(o);
    }
    int query(int o, int nowl, int nowr, int L, int R){
        if(L > R) return 0;
        if(L <= nowl && nowr <= R) return v[o];
        int mid = (nowl + nowr) >> 1;
        int ans = 0;
        if(L <= mid) ans = (ans +0ll+ query(ls(o), nowl, mid, L, R)) % MOD;
        if(R  > mid) ans = (ans +0ll+ query(rs(o), mid + 1, nowr, L, R)) % MOD;
        return ans;
    }
} using SegmentTree::Groot; using SegmentTree::init_s; using SegmentTree::build; using SegmentTree::update; using SegmentTree::query;
int root = 0;
int LCA;
int QueryOnPath(int x, int y){
    int ans = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] > dep[top[y]]) swap(x, y);
        ans = (ans +0ll+ query(root, 1, n, dfn[top[y]], dfn[y])) % MOD;
        y = fa[top[y]];
    }
    if(dep[x] < dep[y]) swap(x, y); LCA = y;
    ans = (ans +0ll+ query(root, 1, n, dfn[y], dfn[x])) % MOD; 
    return ans;
}
void doit(){
    clear();
    n = read(), q = read();
    for(int i = 1; i <= n; i++) NodeVal[i] = read();
    for(int i = 1; i <  n; i++){ int u = read(), v = read(); add(u, v); add(v, u); }
    dfs0(1, 1, 1);
    dfs1(1, 1, 1);
    init_s(); root = Groot();
    build(root, 1, n);
    while(q--){
        int opt = read(), x = read(), y = read();
        if(opt == 1){
            int r = QueryOnPath(x, y);
            int Len = dep[x] + dep[y] - (dep[LCA] << 1) + 1;
            puts(SS[Len] == r ? "Yes" : "No");
        } else{
            update(root, 1, n, dfn[x], y);
        }
    }
}
int main(){
    for(int i = 1; i <= 3e5; i++) SS[i] = ( SS[i - 1] +0ll+ pow(i) ) % MOD;
    int T = read();
    while(T--) doit();
    return 0;
}

CF521E Cycling City

给定一张 $n$ 个点 $m$ 条边的无向简单图。
问图中能否找到两个点，满足这两个点之间有至少三条完全不相交的简单路径。
$n,m \le 2 \times 10^5$ ，图不保证连通

考虑生成树，对原图做一个生成树，考虑每个在生成树外的边，覆盖在树上，树上边被覆盖两次的，即为一种方案

由于树的拓扑结构比图要简单很多，直接思考图的生成树解决图内问题是一个常见思路。

CF547D Mike and Fish

待填

📚 Version History

Source Code Change History

v1 📅 2020-10-19 17:05:04

🔗 Source Hash: 8a8fc399df311c0620a45f107a1a0bca6e37f6b130ecdc0287d077e9ba302c69

Build Logs

Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「杂题记录」IOI2020国家集训队作业-Part-1.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「杂题记录」IOI2020国家集训队作业-Part-1.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../581f3e7c80.pdf.md', '-o', 'cache/581f3e7c80.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawInline (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \usepackage{color}
  \usepackage{fancyvrb}
  \newcommand{\VerbBar}{|}
  \newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
  \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
  % Add ',fontsize=\small' for more characters per line
  \newenvironment{Shaded}{}{}
  \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
  \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}}
  \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
  \newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
  \newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
  \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
  \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\ExtensionTok}[1]{#1}
  \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
  \newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}}
  \newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\NormalTok}[1]{#1}
  \newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
  \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
  \newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
  \newcommand{\RegionMarkerTok}[1]{#1}
  \newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
  \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
  \newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \ifLuaTeX
    \usepackage{luacolor}
    \usepackage[soul]{lua-ul}
  \else
    \usepackage{soul}
    \ifXeTeX
      % soul's \st doesn't work for CJK:
      \usepackage{xeCJKfntef}
      \renewcommand{\st}[1]{\sout{#1}}
    \fi
  \fi
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「题单」IOI2020国家集训队作业 Part 1},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「题单」IOI2020国家集训队作业 Part 1}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-10-19 17:05:04}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  \section{CF505E Mr.~Kitayuta
  vs.~Bamboos}\label{cf505e-mr.-kitayuta-vs.-bamboos}
  
  \begin{itemize}
  \tightlist
  \item
    给定 \(n\) 个数（竹子的高度） \(h_{1 \dots n}\)。
  \item
    你需要进行 \(m\) 轮操作，每轮操作为 \(k\)
    次修改，每次修改可以选择一个数 \(h_i\) 修改为
    \(\max(h_i - p, 0)\)（砸到地下）。
  \item
    每轮操作后每个 \(h_i\) 将会被修改为 \(h_i + a_i\)（每天竹子会生长）。
  \item
    你需要最小化最终 \(h_{1 \dots n}\) 中的最大值。
  \item
    \(n \le 10^5\)，\(m \le 5 \times 10^3\)，\(k \le 10\)
    要求最小化最大值，考虑二分一个最大的高度，将问题转化成可行性问题，即，给出一个高度，问能否使这些竹子最终不超过这个高度。
  \end{itemize}
  
  考虑限制这个问题不平凡的因素：因为每次降低竹子高度的时候不能保证竹子一定降低
  p
  ，也就是说，“砸竹子”这一动作存在浪费。我们考虑尽可能的让“砸竹子”这一动作更少的浪费，即：尽可能在后面的时间点砸竹子，但是无法保证到底是在哪一次砸竹子，有可能已经结束了，没有形式化的计算流程。
  
  可以考虑反向思考，即：假设已经长到
  二分的高度。每次生长操作相当于每次会下落
  \(a_i\)，而每次砸的操作相当于提升了 \(p\) 的高度。
  
  开始时，对每一个竹子计算出其需要多少次会下落到负高度，用堆维护，每次取出最快的可能下落到负高度的
  k 个竹子，进行 “拔高” 操作。然后判断最后的高度是否大于等于\(h_i\)。
  
  其实二分的本质是为了确定“尽可能的靠后砸竹子”的标准。反向思考是为了便于贪心处理策略。
  \#\# code
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{,}\NormalTok{ m}\OperatorTok{,}\NormalTok{ k}\OperatorTok{,}\NormalTok{ p}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ H}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ A}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \PreprocessorTok{\#define mp }\NormalTok{make\_pair}
  \PreprocessorTok{\#define fi }\NormalTok{first}
  \PreprocessorTok{\#define se }\NormalTok{second}
  \DataTypeTok{int}\NormalTok{ height}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{bool}\NormalTok{ check}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ MaxH}\OperatorTok{)\{}
  \NormalTok{    fill}\OperatorTok{(}\NormalTok{height }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ height }\OperatorTok{+} \DecValTok{1} \OperatorTok{+}\NormalTok{ n}\OperatorTok{,}\NormalTok{ MaxH}\OperatorTok{);}
  \NormalTok{    priority\_queue}\OperatorTok{\textless{}}\NormalTok{pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{},}\NormalTok{ vector}\OperatorTok{\textless{}}\NormalTok{pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}} \OperatorTok{\textgreater{}} \OperatorTok{,}\NormalTok{ greater}\OperatorTok{\textless{}}\NormalTok{pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}} \OperatorTok{\textgreater{}} \OperatorTok{\textgreater{}}\NormalTok{ Q}\OperatorTok{;}
      \ControlFlowTok{while}\OperatorTok{(!}\NormalTok{Q}\OperatorTok{.}\NormalTok{empty}\OperatorTok{())}\NormalTok{ Q}\OperatorTok{.}\NormalTok{pop}\OperatorTok{();}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{MaxH }\OperatorTok{{-}}\NormalTok{ m }\OperatorTok{*}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{\textless{}}\NormalTok{ H}\OperatorTok{[}\NormalTok{i}\OperatorTok{])}\NormalTok{ Q}\OperatorTok{.}\NormalTok{push}\OperatorTok{(}\NormalTok{mp}\OperatorTok{(}\NormalTok{ MaxH }\OperatorTok{/}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{],}\NormalTok{ i }\OperatorTok{));}
  
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \OperatorTok{\{}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ k}\OperatorTok{;}\NormalTok{ j}\OperatorTok{++)\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{Q}\OperatorTok{.}\NormalTok{empty}\OperatorTok{())} \ControlFlowTok{return} \KeywordTok{true}\OperatorTok{;}
  \NormalTok{            pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}}\NormalTok{ now }\OperatorTok{=}\NormalTok{ Q}\OperatorTok{.}\NormalTok{top}\OperatorTok{();}\NormalTok{ Q}\OperatorTok{.}\NormalTok{pop}\OperatorTok{();} 
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{now}\OperatorTok{.}\NormalTok{fi }\OperatorTok{\textless{}}\NormalTok{ i}\OperatorTok{)} \ControlFlowTok{return} \KeywordTok{false}\OperatorTok{;}
  \NormalTok{            height}\OperatorTok{[}\NormalTok{now}\OperatorTok{.}\NormalTok{se}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ p}\OperatorTok{;}
  \NormalTok{            now}\OperatorTok{.}\NormalTok{fi }\OperatorTok{=}\NormalTok{ height}\OperatorTok{[}\NormalTok{now}\OperatorTok{.}\NormalTok{se}\OperatorTok{]} \OperatorTok{/}\NormalTok{ A}\OperatorTok{[}\NormalTok{now}\OperatorTok{.}\NormalTok{se}\OperatorTok{];}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{height}\OperatorTok{[}\NormalTok{now}\OperatorTok{.}\NormalTok{se}\OperatorTok{]} \OperatorTok{{-}}\NormalTok{ m }\OperatorTok{*}\NormalTok{ A}\OperatorTok{[}\NormalTok{now}\OperatorTok{.}\NormalTok{se}\OperatorTok{]} \OperatorTok{\textless{}}\NormalTok{ H}\OperatorTok{[}\NormalTok{now}\OperatorTok{.}\NormalTok{se}\OperatorTok{])}\NormalTok{ Q}\OperatorTok{.}\NormalTok{push}\OperatorTok{(}\NormalTok{now}\OperatorTok{);}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{return}\NormalTok{ Q}\OperatorTok{.}\NormalTok{empty}\OperatorTok{();}
  \OperatorTok{\}}
  \DataTypeTok{signed}\NormalTok{ main}\OperatorTok{()\{}
  \NormalTok{    n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ m }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ k }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ p }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();} \CommentTok{// 竹子数 天数 修改次数 最大降低高度 }
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ H}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  
      \DataTypeTok{int}\NormalTok{ L }\OperatorTok{=} \DecValTok{0}\OperatorTok{,}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{,}\NormalTok{ R }\OperatorTok{=} \DecValTok{1}\BuiltInTok{LL} \OperatorTok{\textless{}\textless{}} \DecValTok{60}\OperatorTok{;} \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ L }\OperatorTok{=}\NormalTok{ min}\OperatorTok{(}\NormalTok{L}\OperatorTok{,}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}
      \ControlFlowTok{while}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}}\NormalTok{ R}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=} \OperatorTok{(}\NormalTok{L }\OperatorTok{+}\NormalTok{ R}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{check}\OperatorTok{(}\NormalTok{mid}\OperatorTok{))}\NormalTok{ ans }\OperatorTok{=}\NormalTok{ mid}\OperatorTok{,}\NormalTok{ R }\OperatorTok{=}\NormalTok{ mid}\OperatorTok{;}
          \ControlFlowTok{else}\NormalTok{ L }\OperatorTok{=}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{;}
      \OperatorTok{\}}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%lld\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ ans}\OperatorTok{);}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \section{CF521D Shop}\label{cf521d-shop}
  
  \begin{itemize}
  \tightlist
  \item
    有 \(k\) 个正整数 \(a_{1\dots k}\)。
  \item
    有 \(n\) 个操作，每个操作给定正整数 \(b\)，有三种可能：将 \(a_i\)
    赋值为 \(b\)，将 \(a_i\) 加上 \(b\)，将 \(a_i\) 乘以 \(b\)。
  \item
    你可以从 \(n\) 个操作中选择最多 \(m\) 个操作，并按照一定顺序执行。
  \item
    你的目标是最大化 \(\prod_{i=1}^k a_i\) 的值。
  \item
    \(k,n \le 10^5\)。
  \end{itemize}
  
  化归思想，考虑如果只有乘法，那一定是把操作数字从大到小排序，然后以此操作。
  
  考虑操作顺序，最优的操作一定是先赋值，再加法，最后乘法。其中赋值只可能选相应位置最大的赋值，加法也是从大到小考虑。
  
  显然赋值可以直接转化成加法，而加法如果从大到小考虑也可以直接转化成乘法（乘一个实数）。
  
  这样就把所有操作转化成了乘法。 贪心考虑即可。
  
  最后输出有顺序，应按照上面的策略（先赋值，再加法，最后乘法）以此输出（操作顺序）。
  
  \subsection{code}\label{code}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#include }\ImportTok{\textless{}climits\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstring\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstdio\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cmath\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}iostream\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}algorithm\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}vector\textgreater{}}
  \KeywordTok{using} \KeywordTok{namespace}\NormalTok{ std}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{1e5} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \PreprocessorTok{\#define LL }\DataTypeTok{long}\PreprocessorTok{ }\DataTypeTok{long}
  \DataTypeTok{int}\NormalTok{ read}\OperatorTok{()} \OperatorTok{\{} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{;}\NormalTok{ scanf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d}\StringTok{"}\OperatorTok{,} \OperatorTok{\&}\NormalTok{x}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ x}\OperatorTok{;} \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{,}\NormalTok{ m}\OperatorTok{,}\NormalTok{ k}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ v}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \NormalTok{pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}}\NormalTok{ Give}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \NormalTok{vector}\OperatorTok{\textless{}}\NormalTok{pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{\textgreater{}} \OperatorTok{\textgreater{}}\NormalTok{ add}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \NormalTok{vector}\OperatorTok{\textless{}}\NormalTok{pair}\OperatorTok{\textless{}}\DataTypeTok{double}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}} \OperatorTok{\textgreater{}}\NormalTok{ mul}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \NormalTok{vector}\OperatorTok{\textless{}}\NormalTok{pair}\OperatorTok{\textless{}}\DataTypeTok{double}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}} \OperatorTok{\textgreater{}}\NormalTok{ All}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ T}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ id}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \PreprocessorTok{\#define double }\DataTypeTok{long}\PreprocessorTok{ }\DataTypeTok{double}
  \DataTypeTok{bool}\NormalTok{ ICMP  }\OperatorTok{(}\AttributeTok{const}\NormalTok{ pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}} \OperatorTok{\&}\NormalTok{ x}\OperatorTok{,} \AttributeTok{const}\NormalTok{ pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}} \OperatorTok{\&}\NormalTok{ y}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{x }\OperatorTok{\textgreater{}}\NormalTok{ y}\OperatorTok{);} \OperatorTok{\}}
  \DataTypeTok{bool}\NormalTok{ ICMP\_D}\OperatorTok{(}\AttributeTok{const}\NormalTok{ pair}\OperatorTok{\textless{}}\DataTypeTok{double}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}} \OperatorTok{\&}\NormalTok{ x}\OperatorTok{,} \AttributeTok{const}\NormalTok{ pair}\OperatorTok{\textless{}}\DataTypeTok{double}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}} \OperatorTok{\&}\NormalTok{ y}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{x }\OperatorTok{\textgreater{}}\NormalTok{ y}\OperatorTok{);} \OperatorTok{\}}
  \DataTypeTok{bool}\NormalTok{ MAGIC}\OperatorTok{(}\AttributeTok{const} \DataTypeTok{int} \OperatorTok{\&}\NormalTok{x}\OperatorTok{,} \AttributeTok{const} \DataTypeTok{int} \OperatorTok{\&}\NormalTok{y}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{return}\NormalTok{ T}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{\textless{}}\NormalTok{ T}\OperatorTok{[}\NormalTok{y}\OperatorTok{];} \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{}
  \NormalTok{    k }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ m }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ k}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ v}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \DataTypeTok{int}\NormalTok{ type }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}\NormalTok{ T}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ type}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ a }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ b }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{type }\OperatorTok{==} \DecValTok{1}\OperatorTok{)\{}
  \NormalTok{            Give}\OperatorTok{[}\NormalTok{a}\OperatorTok{]} \OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{Give}\OperatorTok{[}\NormalTok{a}\OperatorTok{],}\NormalTok{ make\_pair}\OperatorTok{(}\NormalTok{b}\OperatorTok{,}\NormalTok{ i}\OperatorTok{));} 
          \OperatorTok{\}} \ControlFlowTok{else} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{type }\OperatorTok{==} \DecValTok{2}\OperatorTok{)\{}
  \NormalTok{            add}\OperatorTok{[}\NormalTok{a}\OperatorTok{].}\NormalTok{push\_back}\OperatorTok{(}\NormalTok{make\_pair}\OperatorTok{(}\NormalTok{b}\OperatorTok{,}\NormalTok{ i}\OperatorTok{));}
          \OperatorTok{\}} \ControlFlowTok{else} \OperatorTok{\{}
  \NormalTok{            mul}\OperatorTok{[}\NormalTok{a}\OperatorTok{].}\NormalTok{push\_back}\OperatorTok{(}\NormalTok{make\_pair}\OperatorTok{((}\DataTypeTok{double}\OperatorTok{)(}\NormalTok{b}\OperatorTok{),}\NormalTok{ i}\OperatorTok{));}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ k}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{Give}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{first}\OperatorTok{)}
  \NormalTok{            add}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{push\_back}\OperatorTok{(}\NormalTok{make\_pair}\OperatorTok{(}\NormalTok{Give}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{first }\OperatorTok{{-}}\NormalTok{ v}\OperatorTok{[}\NormalTok{i}\OperatorTok{],}\NormalTok{ Give}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{second}\OperatorTok{));}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ k}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ sort}\OperatorTok{(}\NormalTok{add}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{begin}\OperatorTok{(),}\NormalTok{ add}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{end}\OperatorTok{(),}\NormalTok{ ICMP}\OperatorTok{);}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ k}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
  \NormalTok{        LL now }\OperatorTok{=}\NormalTok{ v}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}}\NormalTok{ add}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{size}\OperatorTok{();}\NormalTok{ j}\OperatorTok{++)\{}
  \NormalTok{            mul}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{push\_back}\OperatorTok{(} 
  \NormalTok{                make\_pair}\OperatorTok{(} 
                      \OperatorTok{(}\DataTypeTok{double}\OperatorTok{)(}\NormalTok{now }\OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ add}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{].}\NormalTok{first}\OperatorTok{)} \OperatorTok{/} \OperatorTok{(}\DataTypeTok{double}\OperatorTok{)(}\NormalTok{now}\OperatorTok{),}
  \NormalTok{                    add}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{].}\NormalTok{second}
                  \OperatorTok{)} 
              \OperatorTok{);}\NormalTok{ now }\OperatorTok{+=}\NormalTok{ add}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{].}\NormalTok{first}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ k}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}}\NormalTok{ mul}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{size}\OperatorTok{();}\NormalTok{ j}\OperatorTok{++)}\NormalTok{ All}\OperatorTok{.}\NormalTok{push\_back}\OperatorTok{(}\NormalTok{mul}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{]);}
  \NormalTok{    sort}\OperatorTok{(}\NormalTok{All}\OperatorTok{.}\NormalTok{begin}\OperatorTok{(),}\NormalTok{ All}\OperatorTok{.}\NormalTok{end}\OperatorTok{(),}\NormalTok{ ICMP\_D}\OperatorTok{);}
      \DataTypeTok{int}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{ All}\OperatorTok{.}\NormalTok{size}\OperatorTok{();}\NormalTok{ i}\OperatorTok{++)} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{All}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{first }\OperatorTok{\textgreater{}} \DecValTok{1}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ tot}\OperatorTok{++;} \OperatorTok{\}}
  \NormalTok{    tot }\OperatorTok{=}\NormalTok{ min}\OperatorTok{(}\NormalTok{tot}\OperatorTok{,}\NormalTok{ m}\OperatorTok{);}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tot}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ id}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ All}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{].}\NormalTok{second}\OperatorTok{;}
  \NormalTok{    sort}\OperatorTok{(}\NormalTok{id }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ id }\OperatorTok{+} \DecValTok{1} \OperatorTok{+}\NormalTok{ tot}\OperatorTok{,}\NormalTok{ MAGIC}\OperatorTok{);}\NormalTok{  printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ tot}\OperatorTok{);}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tot}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d\%c}\StringTok{"}\OperatorTok{,}\NormalTok{ id}\OperatorTok{[}\NormalTok{i}\OperatorTok{],} \StringTok{" }\SpecialCharTok{\textbackslash{}n}\StringTok{"}\OperatorTok{[}\NormalTok{i }\OperatorTok{==}\NormalTok{ n}\OperatorTok{]);}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \section{CF526F Pudding Monsters}\label{cf526f-pudding-monsters}
  
  \begin{itemize}
  \tightlist
  \item
    给定一个 \(n \times n\) 的棋盘，其中有 \(n\)
    个棋子，每行每列恰好有一个棋子。
  \item
    求有多少个 \(k \times k\) 的子棋盘中恰好有 \(k\) 个棋子。
  \item
    \(n \le 3 \times 10^5\)。
  \end{itemize}
  
  每行每列\textbf{恰好有一个}棋子的棋盘，可以抽象成一个排列。
  而操作也是对于一个排列的一段进行操作的。
  
  题意可以转化为： - 给出一个排列 -
  求连续段数量，即连续的一段，且段中的元素排好序之后必须是公差为\(1\)的等差数列.
  
  \textbf{连续段计数}
  
  考虑如何刻画“\textbf{连续的一段，且段中的元素排好序之后必须是公差为\(1\)的等差数列}”这个条件，可以形式化的定义：
  
  \[\operatorname{MaxVal} - \operatorname{MinVal} = (R - L)\]
  
  即
  
  \[f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) = 0\]
  
  这个条件成立的基础在于，所求数列不能有重复元素，而且也保证了函数\(f_x(L) \ge 0\),
  查询时只需要维护\textbf{最小值}以及最小值的\textbf{数量}即可。
  
  可以考虑枚举一个端点，比如右端点 \(R\)，然后查找有多少符合条件的左端点
  \(L\) ，用线段树维护\(f_R(x)\)在每个点处的函数值。
  
  考虑当\(f_x(L)\) 移动到 \(f_{x + 1}(L)\) 时， 值的变化。变化的值有 \(R\)
  ,
  可能变化的有\(MaxVal, MinVal\)。用单调栈实时维护更新后会波及哪些元素的最小值。事实上，单调栈处理的过程就是在动态维护一个后缀最小/大值数组。
  
  这里有几个与其有相似之处的题目，但是可能做法并不一样，遇到不要想成一样的题目：
  - \href{https://www.luogu.com.cn/problem/P5278}{算术天才⑨与等差数列}
  (不保证序列中一定元素不重复) - 考虑判断一个序列排好序后是否为等差数列 -
  准确做法 - \(\max−\min=(r−l)k\) - 相邻两数差的绝对值的
  \(\operatorname{gcd}\)是 \(k\) - 区间 \([l,r]\) 内的数不重复 -
  概率性做法 - hash思想，维护 \(n\) 次方和 -
  \href{http://www.zhengruioi.com/contest/718/problem/1615}{树上排列(ZROI)}
  (同样不保证元素一定不重复) - 给定一颗 \(n\)
  个点的树。每个点都一个正整数点权 \(A_i\) ，你需要支持以下两种操作： -
  1、询问点 \(x\) 和点 \(y\) 之间的路径上的所有点（包括点 \(x\) 和点 \(y\)
  ）的点权是否构成一个从 \(1\) 开始的排列（即若这条链长度为 \(len\)
  ，那么问点权集合为 \({1,2,⋯,len}\) ）。 - 2、将 \(A_x\) 修改为 \(y\) 。
  - 由于在树上难以判断某区间内的数字不重复，Hash维护n次方和。 -
  给出一个没有重复元素的序列，询问某区间中的元素是否能加入小于\(k\)个元素使其拍好序后构成一个等差数列。
  - 条件变成了
  \[f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) \ge k\]
  -
  \href{http://www.zhengruioi.com/problem/1532}{count(ZROI)}已知一个集合\(S\)中的最大元素为
  \(N\)，
  且这个集合中的元素可以构成一个等差数列，给出一些形如\(x \in S\)、\(x \notin S\)的限制。求最终的集合有多少种情况。
  - 考虑刻画一个等差数列需要什么参数：公差，和每个元素\(\bmod\)
  公差的值。枚举这两个参数，依次计数即可。
  
  （引用正睿的两道题目，不知道是不是有版权问题，如果有，会立即删除（\st{顺便给正睿OI打个广告}））。
  
  \subsection{code}\label{code-1}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ A}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \PreprocessorTok{\#define fir }\NormalTok{first}
  \PreprocessorTok{\#define sec }\NormalTok{second}
  \KeywordTok{namespace}\NormalTok{ SegmentTree}\OperatorTok{\{}
      \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{3e6} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
      \KeywordTok{struct}\NormalTok{ Node}\OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ MIN}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ sMIN}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ tar}\OperatorTok{;}
  \NormalTok{        Node }\KeywordTok{operator} \OperatorTok{+} \OperatorTok{(}\AttributeTok{const}\NormalTok{ Node }\OperatorTok{\&}\NormalTok{ rhs}\OperatorTok{)} \AttributeTok{const} \OperatorTok{\{}
  \NormalTok{            Node res}\OperatorTok{;}
  \NormalTok{            res}\OperatorTok{.}\NormalTok{MIN  }\OperatorTok{=}\NormalTok{ min}\OperatorTok{(}\NormalTok{MIN}\OperatorTok{,}\NormalTok{ rhs}\OperatorTok{.}\NormalTok{MIN}\OperatorTok{);}
  \NormalTok{            res}\OperatorTok{.}\NormalTok{sMIN }\OperatorTok{=}\NormalTok{ MIN }\OperatorTok{==}\NormalTok{ rhs}\OperatorTok{.}\NormalTok{MIN }\OperatorTok{?} \OperatorTok{(}\NormalTok{ sMIN }\OperatorTok{+}\NormalTok{ rhs}\OperatorTok{.}\NormalTok{sMIN}\OperatorTok{)} \OperatorTok{:} \OperatorTok{(}\NormalTok{MIN }\OperatorTok{\textless{}}\NormalTok{ rhs}\OperatorTok{.}\NormalTok{MIN }\OperatorTok{?}\NormalTok{ sMIN }\OperatorTok{:}\NormalTok{ rhs}\OperatorTok{.}\NormalTok{sMIN}\OperatorTok{)} \OperatorTok{;}
              \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}\NormalTok{v}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ ch}\OperatorTok{[}\NormalTok{\_}\OperatorTok{][}\DecValTok{2}\OperatorTok{];}
      \PreprocessorTok{\#define ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{])}
      \PreprocessorTok{\#define rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{])}
      \PreprocessorTok{\#define make }\OperatorTok{(}\NormalTok{tot}\OperatorTok{++,}\PreprocessorTok{ }\NormalTok{ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{0}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{1}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{v}\OperatorTok{[}\NormalTok{tot}\OperatorTok{].}\NormalTok{MIN}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{v}\OperatorTok{[}\NormalTok{tot}\OperatorTok{].}\NormalTok{sMIN}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\DecValTok{0}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{tot}\OperatorTok{)}
      \DataTypeTok{int}\NormalTok{ Groot}\OperatorTok{()} \OperatorTok{\{} \ControlFlowTok{return}\NormalTok{ make}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ maintain}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)} \OperatorTok{\{}
  \NormalTok{        v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{MIN  }\OperatorTok{=}\NormalTok{ min}\OperatorTok{(}\NormalTok{v}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{MIN}\OperatorTok{,}\NormalTok{ v}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{MIN}\OperatorTok{);}
  \NormalTok{        v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{sMIN }\OperatorTok{=}\NormalTok{ v}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{MIN }\OperatorTok{==}\NormalTok{ v}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{MIN }\OperatorTok{?}\NormalTok{ v}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{sMIN }\OperatorTok{+}\NormalTok{ v}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{sMIN }\OperatorTok{:} \OperatorTok{(}\NormalTok{ v}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{MIN }\OperatorTok{\textless{}}\NormalTok{ v}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{MIN }\OperatorTok{?}\NormalTok{ v}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{sMIN }\OperatorTok{:}\NormalTok{ v}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)].}\NormalTok{sMIN }\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ tar}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{MIN }\OperatorTok{+=}\NormalTok{ x}\OperatorTok{;}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{tar }\OperatorTok{+=}\NormalTok{ x}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ pushdown}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{tar}\OperatorTok{)\{}
  \NormalTok{            tar}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{tar}\OperatorTok{);}\NormalTok{ tar}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{tar}\OperatorTok{);}
  \NormalTok{            v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{tar }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ build}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{==}\NormalTok{ R}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{MIN }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{sMIN }\OperatorTok{=} \DecValTok{1}\OperatorTok{;} \ControlFlowTok{return}\OperatorTok{;} \OperatorTok{\}}
          \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=} \OperatorTok{(}\NormalTok{L }\OperatorTok{+}\NormalTok{ R}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;}
  \NormalTok{        ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)} \OperatorTok{=}\NormalTok{ make}\OperatorTok{;}\NormalTok{ rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)} \OperatorTok{=}\NormalTok{ make}\OperatorTok{;}
  \NormalTok{        build}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ L}\OperatorTok{,}\NormalTok{ mid}\OperatorTok{);}\NormalTok{ build}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ R}\OperatorTok{);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ update}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowl}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowr}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textgreater{}}\NormalTok{ R}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}=}\NormalTok{ nowl }\OperatorTok{\&\&}\NormalTok{ nowr }\OperatorTok{\textless{}=}\NormalTok{ R}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ tar}\OperatorTok{(}\NormalTok{o}\OperatorTok{,}\NormalTok{ x}\OperatorTok{);}
          \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=} \OperatorTok{(}\NormalTok{nowl }\OperatorTok{+}\NormalTok{ nowr}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;}\NormalTok{  pushdown}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}=}\NormalTok{ mid}\OperatorTok{)}\NormalTok{ update}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ nowl}\OperatorTok{,}\NormalTok{ mid}\OperatorTok{,}\NormalTok{ L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{,}\NormalTok{ x}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{R  }\OperatorTok{\textgreater{}}\NormalTok{ mid}\OperatorTok{)}\NormalTok{ update}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ nowr}\OperatorTok{,}\NormalTok{ L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{,}\NormalTok{ x}\OperatorTok{);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
  \NormalTok{    Node query}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowl}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowr}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)} \OperatorTok{\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}=}\NormalTok{ nowl }\OperatorTok{\&\&}\NormalTok{ nowr }\OperatorTok{\textless{}=}\NormalTok{ R}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{];}
          \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=} \OperatorTok{(}\NormalTok{nowl }\OperatorTok{+}\NormalTok{ nowr}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;}\NormalTok{ pushdown}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
  \NormalTok{        Node Ans}\OperatorTok{;}\NormalTok{ Ans}\OperatorTok{.}\NormalTok{MIN }\OperatorTok{=}\NormalTok{ INT\_MAX}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}=}\NormalTok{ mid}\OperatorTok{)}\NormalTok{ Ans }\OperatorTok{=}\NormalTok{ Ans }\OperatorTok{+}\NormalTok{ query}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ nowl}\OperatorTok{,}\NormalTok{ mid}\OperatorTok{,}\NormalTok{ L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{R  }\OperatorTok{\textgreater{}}\NormalTok{ mid}\OperatorTok{)}\NormalTok{ Ans }\OperatorTok{=}\NormalTok{ Ans }\OperatorTok{+}\NormalTok{ query}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ nowr}\OperatorTok{,}\NormalTok{ L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{);}
          \ControlFlowTok{return}\NormalTok{ Ans}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ query}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)\{}
  \NormalTok{        Node res }\OperatorTok{=}\NormalTok{ query}\OperatorTok{(}\NormalTok{o}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,}\NormalTok{ L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{);}
          \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{.}\NormalTok{MIN }\OperatorTok{==} \DecValTok{0} \OperatorTok{?}\NormalTok{ res}\OperatorTok{.}\NormalTok{sMIN }\OperatorTok{:} \DecValTok{0}\OperatorTok{;}
      \OperatorTok{\}}
  \OperatorTok{\}}  \KeywordTok{using}\NormalTok{ SegmentTree}\OperatorTok{::}\NormalTok{Groot}\OperatorTok{;} \KeywordTok{using}\NormalTok{ SegmentTree}\OperatorTok{::}\NormalTok{build}\OperatorTok{;} \KeywordTok{using}\NormalTok{ SegmentTree}\OperatorTok{::}\NormalTok{query}\OperatorTok{;} \KeywordTok{using}\NormalTok{ SegmentTree}\OperatorTok{::}\NormalTok{update}\OperatorTok{;}
  \KeywordTok{namespace}\NormalTok{ Mon\_Stack}\OperatorTok{\{}
      \DataTypeTok{int}\NormalTok{ t0t }\OperatorTok{=} \DecValTok{0}\OperatorTok{,}\NormalTok{ t1t }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{    pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}}\NormalTok{ S0}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ S1}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ work}\OperatorTok{(}\DataTypeTok{int} \OperatorTok{*}\NormalTok{A}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ n}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ Ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ root }\OperatorTok{=}\NormalTok{ Groot}\OperatorTok{();}
  \NormalTok{        build}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{);}
  \NormalTok{        S0}\OperatorTok{[}\DecValTok{0}\OperatorTok{].}\NormalTok{fir }\OperatorTok{=}\NormalTok{ S1}\OperatorTok{[}\DecValTok{0}\OperatorTok{].}\NormalTok{fir }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \OperatorTok{\{}
  \NormalTok{            update}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{,} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{);}
              \ControlFlowTok{while}\OperatorTok{(}\NormalTok{t0t }\OperatorTok{!=} \DecValTok{0} \OperatorTok{\&\&}\NormalTok{ S0}\OperatorTok{[}\NormalTok{t0t}\OperatorTok{].}\NormalTok{sec }\OperatorTok{\textgreater{}=}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \OperatorTok{\{}\NormalTok{ update}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,}\NormalTok{ S0}\OperatorTok{[}\NormalTok{t0t }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{].}\NormalTok{fir }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ S0}\OperatorTok{[}\NormalTok{t0t}\OperatorTok{].}\NormalTok{fir}\OperatorTok{,}\NormalTok{  S0}\OperatorTok{[}\NormalTok{t0t}\OperatorTok{].}\NormalTok{sec}\OperatorTok{);}\NormalTok{ t0t}\OperatorTok{{-}{-};} \OperatorTok{\}}
              \ControlFlowTok{while}\OperatorTok{(}\NormalTok{t1t }\OperatorTok{!=} \DecValTok{0} \OperatorTok{\&\&}\NormalTok{ S1}\OperatorTok{[}\NormalTok{t1t}\OperatorTok{].}\NormalTok{sec }\OperatorTok{\textless{}=}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \OperatorTok{\{}\NormalTok{ update}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,}\NormalTok{ S1}\OperatorTok{[}\NormalTok{t1t }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{].}\NormalTok{fir }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ S1}\OperatorTok{[}\NormalTok{t1t}\OperatorTok{].}\NormalTok{fir}\OperatorTok{,} \OperatorTok{{-}}\NormalTok{S1}\OperatorTok{[}\NormalTok{t1t}\OperatorTok{].}\NormalTok{sec}\OperatorTok{);}\NormalTok{ t1t}\OperatorTok{{-}{-};} \OperatorTok{\}}
  \NormalTok{            update}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,}\NormalTok{ S0}\OperatorTok{[}\NormalTok{t0t}\OperatorTok{].}\NormalTok{fir }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ i}\OperatorTok{,} \OperatorTok{{-}}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}
  \NormalTok{            update}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,}\NormalTok{ S1}\OperatorTok{[}\NormalTok{t1t}\OperatorTok{].}\NormalTok{fir }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ i}\OperatorTok{,}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}
              \DataTypeTok{int}\NormalTok{ t }\OperatorTok{=}\NormalTok{ query}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ i}\OperatorTok{);}
  \NormalTok{            Ans }\OperatorTok{+=}\NormalTok{ t}\OperatorTok{;}
  \NormalTok{            S0}\OperatorTok{[++}\NormalTok{t0t}\OperatorTok{]} \OperatorTok{=}\NormalTok{ make\_pair}\OperatorTok{(}\NormalTok{i}\OperatorTok{,}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}\NormalTok{ S1}\OperatorTok{[++}\NormalTok{t1t}\OperatorTok{]} \OperatorTok{=}\NormalTok{ make\_pair}\OperatorTok{(}\NormalTok{i}\OperatorTok{,}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}
          \OperatorTok{\}}
          \ControlFlowTok{return}\NormalTok{ Ans}\OperatorTok{;}
      \OperatorTok{\}}
  \OperatorTok{\}} \KeywordTok{using}\NormalTok{ Mon\_Stack}\OperatorTok{::}\NormalTok{work}\OperatorTok{;}
  \DataTypeTok{signed}\NormalTok{ main}\OperatorTok{()\{}
  \NormalTok{    n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();} \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \OperatorTok{\{} \DataTypeTok{int}\NormalTok{ x }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ y }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}\NormalTok{ A}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{=}\NormalTok{ y}\OperatorTok{;} \OperatorTok{\}}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%lld\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ work}\OperatorTok{(}\NormalTok{A}\OperatorTok{,}\NormalTok{ n}\OperatorTok{));}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#include }\ImportTok{\textless{}climits\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cmath\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstring\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}iostream\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstdio\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}algorithm\textgreater{}}
  \KeywordTok{using} \KeywordTok{namespace}\NormalTok{ std}\OperatorTok{;}
  \PreprocessorTok{\#define int }\DataTypeTok{long}\PreprocessorTok{ }\DataTypeTok{long}\PreprocessorTok{ }
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ MOD }\OperatorTok{=} \FloatTok{1e9} \OperatorTok{+} \DecValTok{7}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_M }\OperatorTok{=} \FloatTok{2e5} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \KeywordTok{inline} \DataTypeTok{int}\NormalTok{ read}\OperatorTok{()} \OperatorTok{\{} \DataTypeTok{char}\NormalTok{ c }\OperatorTok{=}\NormalTok{ getchar}\OperatorTok{();} \DataTypeTok{int}\NormalTok{ sign }\OperatorTok{=} \DecValTok{1}\OperatorTok{;} \DataTypeTok{int}\NormalTok{ x }\OperatorTok{=} \DecValTok{0}\OperatorTok{;} \ControlFlowTok{while}\OperatorTok{(}\NormalTok{c }\OperatorTok{\textgreater{}} \CharTok{\textquotesingle{}9\textquotesingle{}} \OperatorTok{||}\NormalTok{ c }\OperatorTok{\textless{}} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{c}\OperatorTok{==}\CharTok{\textquotesingle{}{-}\textquotesingle{}}\OperatorTok{)}\NormalTok{sign }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{;}\NormalTok{ c }\OperatorTok{=}\NormalTok{ getchar}\OperatorTok{();} \OperatorTok{\}} \ControlFlowTok{while}\OperatorTok{(}\NormalTok{c }\OperatorTok{\textless{}=} \CharTok{\textquotesingle{}9\textquotesingle{}} \OperatorTok{\&\&}\NormalTok{ c }\OperatorTok{\textgreater{}=} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ x }\OperatorTok{*=} \DecValTok{10}\OperatorTok{;}\NormalTok{ x }\OperatorTok{+=}\NormalTok{ c }\OperatorTok{{-}} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{;}\NormalTok{ c }\OperatorTok{=}\NormalTok{ getchar}\OperatorTok{();} \OperatorTok{\}} \ControlFlowTok{return}\NormalTok{ x }\OperatorTok{*}\NormalTok{ sign}\OperatorTok{;} \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ MAX}\OperatorTok{,}\NormalTok{ m}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ have}\OperatorTok{[}\NormalTok{\_M}\OperatorTok{],}\NormalTok{ tht }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ none}\OperatorTok{[}\NormalTok{\_M}\OperatorTok{],}\NormalTok{ tnt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ d}\OperatorTok{[}\NormalTok{\_M}\OperatorTok{],}\NormalTok{ tdt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;} 
  \DataTypeTok{int}\NormalTok{ c}\OperatorTok{[}\NormalTok{\_M}\OperatorTok{];}\CommentTok{//tct = tdt}
  \DataTypeTok{bool}\NormalTok{ CanBe}\OperatorTok{[}\NormalTok{\_M}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ ToL}\OperatorTok{[}\NormalTok{\_M}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ ToR}\OperatorTok{[}\NormalTok{\_M}\OperatorTok{];}
  \DataTypeTok{void}\NormalTok{ divide}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ s}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{)} \OperatorTok{\{}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{*}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ x}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{x }\OperatorTok{\%}\NormalTok{ i }\OperatorTok{==} \DecValTok{0}\OperatorTok{)}\NormalTok{ d}\OperatorTok{[++}\NormalTok{tdt}\OperatorTok{]} \OperatorTok{=}\NormalTok{ i}\OperatorTok{,}\NormalTok{ c}\OperatorTok{[}\NormalTok{tdt}\OperatorTok{]} \OperatorTok{=}\NormalTok{ s }\OperatorTok{\%}\NormalTok{ i}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{i }\OperatorTok{*}\NormalTok{ i }\OperatorTok{!=}\NormalTok{ x}\OperatorTok{)}\NormalTok{ d}\OperatorTok{[++}\NormalTok{tdt}\OperatorTok{]} \OperatorTok{=}\NormalTok{ x }\OperatorTok{/}\NormalTok{ i}\OperatorTok{,}\NormalTok{ c}\OperatorTok{[}\NormalTok{tdt}\OperatorTok{]} \OperatorTok{=}\NormalTok{ s }\OperatorTok{\%}\NormalTok{ d}\OperatorTok{[}\NormalTok{tdt}\OperatorTok{];}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tdt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ CanBe}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \KeywordTok{true}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{signed}\NormalTok{ main}\OperatorTok{()\{}
      \DataTypeTok{int}\NormalTok{ t}\OperatorTok{;}
  \NormalTok{    MAX }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ m }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \DataTypeTok{int}\NormalTok{ type }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{type }\OperatorTok{==} \DecValTok{1}\OperatorTok{)}\NormalTok{ have}\OperatorTok{[++}\NormalTok{tht}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
          \ControlFlowTok{else}\NormalTok{          none}\OperatorTok{[++}\NormalTok{tnt}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \OperatorTok{\}}
  \NormalTok{    sort}\OperatorTok{(}\NormalTok{have }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ have }\OperatorTok{+} \DecValTok{1} \OperatorTok{+}\NormalTok{ tht}\OperatorTok{);}\NormalTok{ sort}\OperatorTok{(}\NormalTok{none }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ none }\OperatorTok{+} \DecValTok{1} \OperatorTok{+}\NormalTok{ tnt}\OperatorTok{);}
      \DataTypeTok{int}\NormalTok{ maxd }\OperatorTok{=}\NormalTok{ INT\_MAX}\OperatorTok{,}\NormalTok{ Sta}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{2}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tht}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \OperatorTok{\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{maxd }\OperatorTok{\textgreater{}}\NormalTok{ have}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{{-}}\NormalTok{ have}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{])\{}
  \NormalTok{            maxd }\OperatorTok{=}\NormalTok{ have}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{{-}}\NormalTok{ have}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{];}
  \NormalTok{            Sta }\OperatorTok{=}\NormalTok{ have}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{];}
          \OperatorTok{\}}
      \OperatorTok{\}}
  \NormalTok{    divide}\OperatorTok{(}\NormalTok{Sta}\OperatorTok{,}\NormalTok{ maxd}\OperatorTok{);}
  
      \CommentTok{/* 公差 及 特征 检查   */}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tht}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ tdt}\OperatorTok{;}\NormalTok{ j}\OperatorTok{++)\{}
              \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{CanBe}\OperatorTok{[}\NormalTok{j}\OperatorTok{])} \ControlFlowTok{continue}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{have}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{\%}\NormalTok{ d}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{!=}\NormalTok{ c}\OperatorTok{[}\NormalTok{j}\OperatorTok{])}\NormalTok{ CanBe}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{=} \KeywordTok{false}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{2}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tht}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \DataTypeTok{int}\NormalTok{ D }\OperatorTok{=}\NormalTok{ have}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{{-}}\NormalTok{ have}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{];}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ tdt}\OperatorTok{;}\NormalTok{ j}\OperatorTok{++)\{}
              \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{CanBe}\OperatorTok{[}\NormalTok{j}\OperatorTok{])} \ControlFlowTok{continue}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{D }\OperatorTok{\%}\NormalTok{ d}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{!=} \DecValTok{0}\OperatorTok{)}\NormalTok{ CanBe}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{=} \KeywordTok{false}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}
  \NormalTok{    t }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tdt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{CanBe}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        d}\OperatorTok{[++}\NormalTok{t}\OperatorTok{]} \OperatorTok{=}\NormalTok{ d}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
  \NormalTok{        c}\OperatorTok{[}\NormalTok{  t}\OperatorTok{]} \OperatorTok{=}\NormalTok{ c}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
  \NormalTok{        CanBe}\OperatorTok{[}\NormalTok{t}\OperatorTok{]} \OperatorTok{=} \KeywordTok{true}\OperatorTok{;}
      \OperatorTok{\}}\NormalTok{ tdt }\OperatorTok{=}\NormalTok{ t}\OperatorTok{;}
      \CommentTok{/* 公差 及 特征 检查   完成*/}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tdt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \OperatorTok{\{} 
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{CanBe}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \OperatorTok{\{}
  \NormalTok{            ToL}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(}\NormalTok{c}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{==} \DecValTok{0} \OperatorTok{?}\NormalTok{ d}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{:}\NormalTok{ c}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \OperatorTok{{-}} \DecValTok{1}\OperatorTok{;}
              \DataTypeTok{int}\NormalTok{ t }\OperatorTok{=}\NormalTok{ MAX }\OperatorTok{\%}\NormalTok{ d}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{t }\OperatorTok{==}\NormalTok{ c}\OperatorTok{[}\NormalTok{i}\OperatorTok{])}\NormalTok{ ToR}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ MAX }\OperatorTok{+} \DecValTok{1}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{t  }\OperatorTok{\textgreater{}}\NormalTok{ c}\OperatorTok{[}\NormalTok{i}\OperatorTok{])}\NormalTok{ ToR}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ MAX }\OperatorTok{{-}} \OperatorTok{(}\NormalTok{t }\OperatorTok{{-}}\NormalTok{ c}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \OperatorTok{+} \DecValTok{1}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{t  }\OperatorTok{\textless{}}\NormalTok{ c}\OperatorTok{[}\NormalTok{i}\OperatorTok{])}\NormalTok{ ToR}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ MAX }\OperatorTok{{-}}\NormalTok{ d}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+} \OperatorTok{(}\NormalTok{c}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{{-}}\NormalTok{ t}\OperatorTok{)} \OperatorTok{+} \DecValTok{1}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}
  \NormalTok{    t }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tdt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{CanBe}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        d}\OperatorTok{[++}\NormalTok{t}\OperatorTok{]} \OperatorTok{=}\NormalTok{ d}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
  \NormalTok{        c}\OperatorTok{[}\NormalTok{  t}\OperatorTok{]} \OperatorTok{=}\NormalTok{ c}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
  \NormalTok{        CanBe}\OperatorTok{[}\NormalTok{t}\OperatorTok{]} \OperatorTok{=} \KeywordTok{true}\OperatorTok{;}
      \OperatorTok{\}}\NormalTok{ tdt }\OperatorTok{=}\NormalTok{ t}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ MINS }\OperatorTok{=}\NormalTok{ have}\OperatorTok{[}\DecValTok{1}\OperatorTok{],}\NormalTok{ MAXE }\OperatorTok{=}\NormalTok{ have}\OperatorTok{[}\NormalTok{tht}\OperatorTok{];}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tnt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \DataTypeTok{int}\NormalTok{ now }\OperatorTok{=}\NormalTok{ none}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ tdt}\OperatorTok{;}\NormalTok{ j}\OperatorTok{++)\{}
              \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{CanBe}\OperatorTok{[}\NormalTok{j}\OperatorTok{])} \ControlFlowTok{continue}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{now }\OperatorTok{\%}\NormalTok{ d}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{==}\NormalTok{ c}\OperatorTok{[}\NormalTok{j}\OperatorTok{])\{}
                  \ControlFlowTok{if}\OperatorTok{(}\NormalTok{now }\OperatorTok{\textless{}}\NormalTok{ MINS}\OperatorTok{)}
  \NormalTok{                    ToL}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{ToL}\OperatorTok{[}\NormalTok{j}\OperatorTok{],}\NormalTok{ now}\OperatorTok{);}
                  \ControlFlowTok{else} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{now }\OperatorTok{\textgreater{}}\NormalTok{ MAXE}\OperatorTok{)}
  \NormalTok{                    ToR}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{=}\NormalTok{ min}\OperatorTok{(}\NormalTok{ToR}\OperatorTok{[}\NormalTok{j}\OperatorTok{],}\NormalTok{ now}\OperatorTok{);}
                  \ControlFlowTok{else}\NormalTok{ CanBe}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{=} \KeywordTok{false}\OperatorTok{;}
              \OperatorTok{\}}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tdt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ToL}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{\textgreater{}}\NormalTok{ MINS }\OperatorTok{||}\NormalTok{ ToR}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{\textless{}}\NormalTok{ MAXE}\OperatorTok{)}\NormalTok{ CanBe}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \KeywordTok{false}\OperatorTok{;} \ControlFlowTok{else}\NormalTok{ ToL}\OperatorTok{[}\NormalTok{i}\OperatorTok{]++,}\NormalTok{ ToR}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{{-}{-};}
      \CommentTok{/* 非法数字存在性检查 */}
      \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ tdt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{CanBe}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \ControlFlowTok{continue}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ k }\OperatorTok{=} \OperatorTok{(}  \OperatorTok{(}\NormalTok{MINS }\OperatorTok{{-}}\NormalTok{ ToL}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \OperatorTok{/}\NormalTok{ d}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+} \DecValTok{1}\OperatorTok{)} \OperatorTok{*} \OperatorTok{(} \OperatorTok{(}\NormalTok{ToR}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{{-}}\NormalTok{ MAXE}\OperatorTok{)} \OperatorTok{/}\NormalTok{ d}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+} \DecValTok{1}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;} \CommentTok{// }\AlertTok{TODO}\CommentTok{;}
  \NormalTok{        ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{+}\NormalTok{ k}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
      \OperatorTok{\}}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%lld}\StringTok{"}\OperatorTok{,}\NormalTok{ ans}\OperatorTok{);}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#include }\ImportTok{\textless{}climits\textgreater{}}\PreprocessorTok{ }
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstring\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cmath\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}iostream\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}algorithm\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}vector\textgreater{}}
  \KeywordTok{inline} \DataTypeTok{int}\NormalTok{ read}\OperatorTok{()} \OperatorTok{\{} \DataTypeTok{char}\NormalTok{ c }\OperatorTok{=}\NormalTok{ getchar}\OperatorTok{();} \DataTypeTok{int}\NormalTok{ sign }\OperatorTok{=} \DecValTok{1}\OperatorTok{;} \DataTypeTok{int}\NormalTok{ x }\OperatorTok{=} \DecValTok{0}\OperatorTok{;} \ControlFlowTok{while}\OperatorTok{(}\NormalTok{c }\OperatorTok{\textgreater{}} \CharTok{\textquotesingle{}9\textquotesingle{}} \OperatorTok{||}\NormalTok{ c }\OperatorTok{\textless{}} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{c}\OperatorTok{==}\CharTok{\textquotesingle{}{-}\textquotesingle{}}\OperatorTok{)}\NormalTok{sign }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{;}\NormalTok{ c }\OperatorTok{=}\NormalTok{ getchar}\OperatorTok{();} \OperatorTok{\}} \ControlFlowTok{while}\OperatorTok{(}\NormalTok{c }\OperatorTok{\textless{}=} \CharTok{\textquotesingle{}9\textquotesingle{}} \OperatorTok{\&\&}\NormalTok{ c }\OperatorTok{\textgreater{}=} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ x }\OperatorTok{*=} \DecValTok{10}\OperatorTok{;}\NormalTok{ x }\OperatorTok{+=}\NormalTok{ c }\OperatorTok{{-}} \CharTok{\textquotesingle{}0\textquotesingle{}}\OperatorTok{;}\NormalTok{ c }\OperatorTok{=}\NormalTok{ getchar}\OperatorTok{();} \OperatorTok{\}} \ControlFlowTok{return}\NormalTok{ x }\OperatorTok{*}\NormalTok{ sign}\OperatorTok{;} \OperatorTok{\}}
  \KeywordTok{using} \KeywordTok{namespace}\NormalTok{ std}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{6e5} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ base }\OperatorTok{=} \DecValTok{15}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ MOD }\OperatorTok{=} \DecValTok{1020031005}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ SS}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ pow}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ a}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ b }\OperatorTok{=}\NormalTok{ base}\OperatorTok{)\{} \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{1}\OperatorTok{;} \ControlFlowTok{while}\OperatorTok{(}\NormalTok{b}\OperatorTok{)\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{b }\OperatorTok{\&} \DecValTok{1}\OperatorTok{)}\NormalTok{ ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ a}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}\NormalTok{ a }\OperatorTok{=} \OperatorTok{(}\NormalTok{a }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ a}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}\NormalTok{ b }\OperatorTok{\textgreater{}\textgreater{}=} \DecValTok{1}\OperatorTok{;} \OperatorTok{\}} \ControlFlowTok{return}\NormalTok{ ans}\OperatorTok{;} \OperatorTok{\}}
  
  \DataTypeTok{int}\NormalTok{ head}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ NodeVal}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \KeywordTok{struct}\NormalTok{ edges}\OperatorTok{\{}
      \DataTypeTok{int}\NormalTok{ node}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ nxt}\OperatorTok{;}
  \OperatorTok{\}}\NormalTok{edge}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ add}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ u}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ v}\OperatorTok{)\{}
  \NormalTok{    tot}\OperatorTok{++;}
  \NormalTok{    edge}\OperatorTok{[}\NormalTok{tot}\OperatorTok{].}\NormalTok{node }\OperatorTok{=}\NormalTok{ v}\OperatorTok{;}
  \NormalTok{    edge}\OperatorTok{[}\NormalTok{tot}\OperatorTok{].}\NormalTok{nxt  }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{u}\OperatorTok{];}
  \NormalTok{    head}\OperatorTok{[}\NormalTok{u}\OperatorTok{]}        \OperatorTok{=}\NormalTok{ tot}\OperatorTok{;}
  \OperatorTok{\}}
  
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{,}\NormalTok{ q}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ dep}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ fa}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ dfn}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ rnk}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ top}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ son}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ si}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ dfc }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ dfs0}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ now}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ dp}\OperatorTok{)\{}
      \DataTypeTok{int} \OperatorTok{\&}\NormalTok{S }\OperatorTok{=}\NormalTok{ si}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;} \DataTypeTok{int} \OperatorTok{\&}\NormalTok{Mid }\OperatorTok{=}\NormalTok{ son}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ fa}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=}\NormalTok{ f}\OperatorTok{;}\NormalTok{ dep}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=}\NormalTok{ dp}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{ i }\OperatorTok{;}\NormalTok{ i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ex }\OperatorTok{==}\NormalTok{ f}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        dfs0}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ now}\OperatorTok{,}\NormalTok{ dp }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}\NormalTok{ S }\OperatorTok{+=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{];}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{]} \OperatorTok{\textgreater{}}\NormalTok{ si}\OperatorTok{[}\NormalTok{Mid}\OperatorTok{])}\NormalTok{ Mid }\OperatorTok{=}\NormalTok{ ex}\OperatorTok{;}
      \OperatorTok{\}} \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{Mid}\OperatorTok{)}\NormalTok{ Mid }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{void}\NormalTok{ dfs1}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ now}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ tp}\OperatorTok{)\{}
  \NormalTok{    dfn}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=} \OperatorTok{++}\NormalTok{dfc}\OperatorTok{;}\NormalTok{ rnk}\OperatorTok{[}\NormalTok{dfc}\OperatorTok{]} \OperatorTok{=}\NormalTok{ now}\OperatorTok{;}
  \NormalTok{    top}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{=}\NormalTok{ tp}\OperatorTok{;}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{son}\OperatorTok{[}\NormalTok{now}\OperatorTok{])}\NormalTok{ dfs1}\OperatorTok{(}\NormalTok{son}\OperatorTok{[}\NormalTok{now}\OperatorTok{],}\NormalTok{ now}\OperatorTok{,}\NormalTok{ tp}\OperatorTok{);}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{now}\OperatorTok{];}\NormalTok{ i }\OperatorTok{;}\NormalTok{ i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ex }\OperatorTok{==}\NormalTok{ f }\OperatorTok{||}\NormalTok{ ex }\OperatorTok{==}\NormalTok{ son}\OperatorTok{[}\NormalTok{now}\OperatorTok{])} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        dfs1}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ now}\OperatorTok{,}\NormalTok{ ex}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{void}\NormalTok{ clear}\OperatorTok{()\{}
  \NormalTok{    memset}\OperatorTok{(}\NormalTok{head}\OperatorTok{,} \DecValTok{0}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\NormalTok{head}\OperatorTok{));}
  \NormalTok{    dfn}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ rnk}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ si}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ top}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ son}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{    tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{    dfc }\OperatorTok{=} \DecValTok{0}\OperatorTok{;} 
  \OperatorTok{\}}
  \KeywordTok{namespace}\NormalTok{ SegmentTree}\OperatorTok{\{}
      \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{3e6} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ ch}\OperatorTok{[}\NormalTok{\_}\OperatorTok{][}\DecValTok{2}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ v}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \PreprocessorTok{\#define make }\OperatorTok{(}\NormalTok{tot}\OperatorTok{++,}\PreprocessorTok{ }\NormalTok{ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{0}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{1}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{v}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\DecValTok{0}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{tot}\OperatorTok{);}
      \PreprocessorTok{\#define ls}\OperatorTok{(}\NormalTok{x}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{x}\OperatorTok{][}\DecValTok{0}\OperatorTok{])}
      \PreprocessorTok{\#define rs}\OperatorTok{(}\NormalTok{x}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{x}\OperatorTok{][}\DecValTok{1}\OperatorTok{])}
      \PreprocessorTok{\#define maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{v}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]}\PreprocessorTok{ }\OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\PreprocessorTok{ }\NormalTok{v}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)])}\PreprocessorTok{ }\OperatorTok{\%}\PreprocessorTok{ }\NormalTok{MOD}\PreprocessorTok{ }\OperatorTok{)}
      \DataTypeTok{void}\NormalTok{ init\_s}\OperatorTok{()} \OperatorTok{\{}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{  Groot}\OperatorTok{()\{} \ControlFlowTok{return}\NormalTok{ make}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ build}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{==}\NormalTok{ R}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{(}\DataTypeTok{void}\OperatorTok{)(}\NormalTok{v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ pow}\OperatorTok{(}\NormalTok{NodeVal}\OperatorTok{[}\NormalTok{rnk}\OperatorTok{[}\NormalTok{L}\OperatorTok{]]));}
          \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=} \OperatorTok{(}\NormalTok{L }\OperatorTok{+}\NormalTok{ R}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;}
  \NormalTok{        ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)} \OperatorTok{=}\NormalTok{ make}\OperatorTok{;}\NormalTok{ rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)} \OperatorTok{=}\NormalTok{ make}\OperatorTok{;}
  \NormalTok{        build}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ L}\OperatorTok{,}\NormalTok{ mid}\OperatorTok{);}\NormalTok{ build}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ R}\OperatorTok{);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ update}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowl}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowr}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ p}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{nowl }\OperatorTok{==}\NormalTok{ nowr}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{(}\DataTypeTok{void}\OperatorTok{)(}\NormalTok{v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ pow}\OperatorTok{(}\NormalTok{x}\OperatorTok{));}
          \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=} \OperatorTok{(}\NormalTok{nowl }\OperatorTok{+}\NormalTok{ nowr}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{p }\OperatorTok{\textless{}=}\NormalTok{ mid}\OperatorTok{)}\NormalTok{ update}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ nowl}\OperatorTok{,}\NormalTok{ mid}\OperatorTok{,}\NormalTok{ p}\OperatorTok{,}\NormalTok{ x}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{p  }\OperatorTok{\textgreater{}}\NormalTok{ mid}\OperatorTok{)}\NormalTok{ update}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ nowr}\OperatorTok{,}\NormalTok{ p}\OperatorTok{,}\NormalTok{ x}\OperatorTok{);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ query}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowl}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowr}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textgreater{}}\NormalTok{ R}\OperatorTok{)} \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}=}\NormalTok{ nowl }\OperatorTok{\&\&}\NormalTok{ nowr }\OperatorTok{\textless{}=}\NormalTok{ R}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{];}
          \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=} \OperatorTok{(}\NormalTok{nowl }\OperatorTok{+}\NormalTok{ nowr}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}=}\NormalTok{ mid}\OperatorTok{)}\NormalTok{ ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ query}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ nowl}\OperatorTok{,}\NormalTok{ mid}\OperatorTok{,}\NormalTok{ L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{))} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{R  }\OperatorTok{\textgreater{}}\NormalTok{ mid}\OperatorTok{)}\NormalTok{ ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ query}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ nowr}\OperatorTok{,}\NormalTok{ L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{))} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
          \ControlFlowTok{return}\NormalTok{ ans}\OperatorTok{;}
      \OperatorTok{\}}
  \OperatorTok{\}} \KeywordTok{using}\NormalTok{ SegmentTree}\OperatorTok{::}\NormalTok{Groot}\OperatorTok{;} \KeywordTok{using}\NormalTok{ SegmentTree}\OperatorTok{::}\NormalTok{init\_s}\OperatorTok{;} \KeywordTok{using}\NormalTok{ SegmentTree}\OperatorTok{::}\NormalTok{build}\OperatorTok{;} \KeywordTok{using}\NormalTok{ SegmentTree}\OperatorTok{::}\NormalTok{update}\OperatorTok{;} \KeywordTok{using}\NormalTok{ SegmentTree}\OperatorTok{::}\NormalTok{query}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ root }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ LCA}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ QueryOnPath}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ y}\OperatorTok{)\{}
      \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{while}\OperatorTok{(}\NormalTok{top}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{!=}\NormalTok{ top}\OperatorTok{[}\NormalTok{y}\OperatorTok{])\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{dep}\OperatorTok{[}\NormalTok{top}\OperatorTok{[}\NormalTok{x}\OperatorTok{]]} \OperatorTok{\textgreater{}}\NormalTok{ dep}\OperatorTok{[}\NormalTok{top}\OperatorTok{[}\NormalTok{y}\OperatorTok{]])}\NormalTok{ swap}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);}
  \NormalTok{        ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ query}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,}\NormalTok{ dfn}\OperatorTok{[}\NormalTok{top}\OperatorTok{[}\NormalTok{y}\OperatorTok{]],}\NormalTok{ dfn}\OperatorTok{[}\NormalTok{y}\OperatorTok{]))} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
  \NormalTok{        y }\OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{top}\OperatorTok{[}\NormalTok{y}\OperatorTok{]];}
      \OperatorTok{\}}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{dep}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{\textless{}}\NormalTok{ dep}\OperatorTok{[}\NormalTok{y}\OperatorTok{])}\NormalTok{ swap}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);}\NormalTok{ LCA }\OperatorTok{=}\NormalTok{ y}\OperatorTok{;}
  \NormalTok{    ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ query}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,}\NormalTok{ dfn}\OperatorTok{[}\NormalTok{y}\OperatorTok{],}\NormalTok{ dfn}\OperatorTok{[}\NormalTok{x}\OperatorTok{]))} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;} 
      \ControlFlowTok{return}\NormalTok{ ans}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{void}\NormalTok{ doit}\OperatorTok{()\{}
  \NormalTok{    clear}\OperatorTok{();}
  \NormalTok{    n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ q }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ NodeVal}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{  n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{} \DataTypeTok{int}\NormalTok{ u }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ v }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}\NormalTok{ add}\OperatorTok{(}\NormalTok{u}\OperatorTok{,}\NormalTok{ v}\OperatorTok{);}\NormalTok{ add}\OperatorTok{(}\NormalTok{v}\OperatorTok{,}\NormalTok{ u}\OperatorTok{);} \OperatorTok{\}}
  \NormalTok{    dfs0}\OperatorTok{(}\DecValTok{1}\OperatorTok{,} \DecValTok{1}\OperatorTok{,} \DecValTok{1}\OperatorTok{);}
  \NormalTok{    dfs1}\OperatorTok{(}\DecValTok{1}\OperatorTok{,} \DecValTok{1}\OperatorTok{,} \DecValTok{1}\OperatorTok{);}
  \NormalTok{    init\_s}\OperatorTok{();}\NormalTok{ root }\OperatorTok{=}\NormalTok{ Groot}\OperatorTok{();}
  \NormalTok{    build}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{);}
      \ControlFlowTok{while}\OperatorTok{(}\NormalTok{q}\OperatorTok{{-}{-})\{}
          \DataTypeTok{int}\NormalTok{ opt }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ x }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ y }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{opt }\OperatorTok{==} \DecValTok{1}\OperatorTok{)\{}
              \DataTypeTok{int}\NormalTok{ r }\OperatorTok{=}\NormalTok{ QueryOnPath}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);}
              \DataTypeTok{int}\NormalTok{ Len }\OperatorTok{=}\NormalTok{ dep}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{+}\NormalTok{ dep}\OperatorTok{[}\NormalTok{y}\OperatorTok{]} \OperatorTok{{-}} \OperatorTok{(}\NormalTok{dep}\OperatorTok{[}\NormalTok{LCA}\OperatorTok{]} \OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{)} \OperatorTok{+} \DecValTok{1}\OperatorTok{;}
  \NormalTok{            puts}\OperatorTok{(}\NormalTok{SS}\OperatorTok{[}\NormalTok{Len}\OperatorTok{]} \OperatorTok{==}\NormalTok{ r }\OperatorTok{?} \StringTok{"Yes"} \OperatorTok{:} \StringTok{"No"}\OperatorTok{);}
          \OperatorTok{\}} \ControlFlowTok{else}\OperatorTok{\{}
  \NormalTok{            update}\OperatorTok{(}\NormalTok{root}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,}\NormalTok{ dfn}\OperatorTok{[}\NormalTok{x}\OperatorTok{],}\NormalTok{ y}\OperatorTok{);}
          \OperatorTok{\}}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=} \FloatTok{3e5}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ SS}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(}\NormalTok{ SS}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ pow}\OperatorTok{(}\NormalTok{i}\OperatorTok{)} \OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ T }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \ControlFlowTok{while}\OperatorTok{(}\NormalTok{T}\OperatorTok{{-}{-})}\NormalTok{ doit}\OperatorTok{();}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \section{CF521E Cycling City}\label{cf521e-cycling-city}
  
  \begin{itemize}
  \tightlist
  \item
    给定一张 \(n\) 个点 \(m\) 条边的无向简单图。
  \item
    问图中能否找到两个点，满足这两个点之间有至少三条完全不相交的简单路径。
  \item
    \(n,m \le 2 \times 10^5\)，图不保证连通
  \end{itemize}
  
  考虑生成树，对原图做一个生成树，考虑每个在生成树外的边，覆盖在树上，树上边被覆盖两次的，即为一种方案
  
  由于树的拓扑结构比图要简单很多，直接思考图的生成树解决图内问题是一个常见思路。
  
  \section{CF547D Mike and Fish}\label{cf547d-mike-and-fish}
  
  \textbf{待填}
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 186.
  
  [2] [3]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 311.
  
  Missing character: There is no ⑨ (U+2468) in font Latin Modern Roman 10 Regular
  /OT:script=latn;language=dflt;mapping=tex-text;!
  [4] [5] [6] [7] [8] [9] [10] [11] [12]
  (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (12 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 186.
  
  [2] [3]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 311.
  
  Missing character: There is no ⑨ (U+2468) in font Latin Modern Roman 10 Regular
  /OT:script=latn;language=dflt;mapping=tex-text;!
  [4] [5] [6] [7] [8] [9] [10] [11] [12]
  (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (12 pages).
  Transcript written on .../input.log.
[WARNING] Missing character: There is no ⑨ (U+2468) (U+2468) in font Latin Modern Roman 10 Regular