头像

心里没有一点AC数

前端狗 算法笔记 www.fogsail.net




离线:22小时前


最近来访(1527)
用户头像
yxc的小迷妹
用户头像
etuc
用户头像
C++djr
用户头像
TLEWing
用户头像
chr9875117
用户头像
bre
用户头像
想成为加持良治的老鼠人
用户头像
L-China
用户头像
PerfectLife
用户头像
123321123321123321123321123321
用户头像
Aaron_85
用户头像
L_B_L
用户头像
lyles
用户头像
感谢经历
用户头像
君故
用户头像
沐沐yee
用户头像
鳕鱼饭
用户头像
1357649762
用户头像
wrtgj
用户头像
路明泽


Atcoder 的 AC Library 中封装了线段树模板,在需要构建线段树的时候,需要像使用 STL 标准库那样引入即可。注意是如何实例化的,下面通过几个例子来说明

部分方法和单点修改一样
不动脑子地写线段树——单点修改

源码链接

线段树区间修改

线段树区间修改同样是针对单群而言的,这里引入一个映射集 $F$
满足 $(F:S \to S, \quad S \times S \to S, \quad e\in S) $

  • $F$ 中存在一个恒等映射 $id(x)$,满足对于所有 $x \in S$,$id(x) = x$ 成立

  • 满足闭包,即对于 $f, g \in F$,那么 $g \circ f \in F$

  • 积性,对于操作 *(我们之前用 op 定义了),对于 $x, y \in S$,
    $$f(x * y) = f(x) * f(y)$$

线段树区间修改可以执行以下操作

  • 求一个区间 $[l, r]$ 中 $ op(a_l, \cdots, a_r) $ 的结果

  • 对区间 $[l, r]$ 中所有元素 $x$ 执行映射 $x \to f(x), f \in F$

构造函数和方法

(1) lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
(2) lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> v);
  • S, op, e 和单点修改的一样
    S 表示节点元素类型,op对应pull操作,e是幺元

  • F映射的类型,比如让区间都加上一个数,F <=> long long
    因为 long long add 即可表示区间加运算
    如果涉及两种操作,比如区间加,区间乘,那么F可以定义为一个结构体
    struct F { long long mul, add; };

  • mapping 是映射规则,形式为 S mapping(F f, S x),返回 $f(x)$
    值得注意的是,这里的F f表示什么?
    可以理解为f线段树懒标记,可以是 add, mul,... 等等
    F懒标记的类型,比如让区间所有数都+dd是一个long long
    那么就可以如下声明(参数f可以理解为tag

对于 $x$ 节点表示的区间,$x \to f(x)$

// 仅执行区间加法
struct S {
 long long sum, len;
};
S mapping(long long f, S x) {
 return S{x.sum + f*x.len, x.len};
}

容易看出,mapping实际上规定了一个区间怎么打懒标记

  • composition 规定了 $f\circ g$ 的规则
    假设只有一种操作,比如就是区间加,考虑 F composition(F f1, F f2)
    如果懒标记是long long类型的,就是 ll compositon(ll f1, ll f2)
    表示的意义是,先加上懒标记f2,再加上f1,可以如下声明
long long composition(long long f1, long long f2) {
  return f1 + f2;
}

复杂的复合操作如下,比如我们需要执行区间加和区间乘,规定

struct F {
  long long mul, add;
};
S mapping(F f, S x) {
  return S{ x.sum*f.mul + x.len*f.add, x.len };
};

说明,注意如果同时有加法和乘法两种操作
只有加法的时候,我们可以定义变换 F f(add, 1)
只有乘法的时候,类似定义变换 F f(0, mul),这样两种操作可以统一起来

那么对于复合操作(F f, F g),$f\circ g$ 可以如下声明

$$
g(x) = x\cdot g.mul + g.add \\
f(g(x)) = (x\cdot g.mul) \cdot f.mul + f.add
$$

从而 f(g(x)) = f.mul*g.mul*x + f.mul*g.add+f.add

F composition(F f, F g) {
  return F{ f.mul*g.mul, f.mul*g.add+f.add };
}
  • F id() 定义了恒等变换
    如果同时有加法和乘法两种操作,那么恒等变换就是
F id() {
  return F{ 1, 0 };
}
// x = x*1 + 0

set, get

void seg.set(int p, S x)
S seg.get(int p)

prod

S seg.prod(int l, int r)

返回 op(a[l], a[l+1], ..., a[r-1])的结果,如果 l = r 返回 e()

all_prod

S seg.all_prod()

返回 op(a[0], a[1], ..., a[n-1])的结果,n = 0 返回 e()

apply

(1) void seg.apply(int p, F f)
(2) void seg.apply(int l, int r, F f)

执行单点修改,区间修改
特别地,区间修改,对所有的 i = [l, l+1,..., r-1]
执行 $a[i] \to f(a[i]) $

max_right

(1) int seg.max_right<g>(int l)
(2) int seg.max_right<G>(int l, G g)
  • G 是一个函数对象,一般来说,返回的是一个bool类型
  • 必须定义 bool g(S x),并执行线段树二分
    S是线段树的节点数据类型

该函数的返回值r,满足
r = l(此时没找到),或者 g( op(a[l], a[l+1], ..., a[r-1]) ) = true
r = n(此时到end一整段都满足),或者 g( op(a[l], a[l+1], ..., a[r]) ) = false

min_left

(1) int seg.min_left<g>(int r)
(2) int seg.min_left<G>(int r, G g)
  • 同样需要定义 bool g(S x) 来执行线段树二分
    S 是线段树节点数据类型

该函数的返回值是一个 l,满足

  • l = r(此时没找到),或者 g( op(a[l], a[l+1], ..., a[r-1]) ) = true
  • l = 0(此时到begin一整段都满足),或者 g( op(a[l-1], a[l], ..., a[r-1]) ) = false

区间修改的例子

给定 $ a_1, a_2, \cdots, a_n $,支持 q 个操作

  • 1 l r d,给区间 [l, r] 所有数加上 d
  • 2 l r d,给区间 [l, r] 所有数乘上 d
  • 3 l r d,给区间 [l, r] 所有数赋值为 d
  • 4 l r,查询 [l, r] 区间和,并对 ${10^9+7}$ 取模

算法实现

// mint 是取模数类
struct S {
    mint sum;
    int len;
};

S op(S a, S b) {
    return S{a.sum + b.sum, a.len + b.len};
}

S e() {
    return {0, 0};
}

struct F {
    mint mul, add;
};

S mapping(F f, S x) {
    return S{ x.sum*f.mul + mint(x.len)*f.add, x.len };
}

F composition(F f, F g) {
    return F{ f.mul*g.mul, f.mul*g.add + f.add };
}

F id() {
    return F{1, 0};
}

int main() {
    // 部分代码省略
    vector<S> a(n);

    for (int i = 0; i < n; i++) {
        int x; scanf("%d", &x);
        a[i] = S{ mint(x), 1 };
    }

    lazy_segtree<S, op, e, F, mapping, composition, id> tr(a);

    while (q--) {
        // 仅以区间乘法为例子
        F f = F{mint(d), mint(0)};
        tr.apply(l, r+1, f);
    }
}



Atcoder 的 AC Library 中封装了线段树模板,在需要构建线段树的时候,需要像使用 STL 标准库那样引入即可。注意是如何实例化的,下面通过几个例子来说明

源码链接

线段树单点修改

线段树可以看作是为单群建立的数据结构,单群所需要满足的性质有

  • $ a, b, c \in S $,有结合律成立,$ (a \cdot b) \cdot c = a \cdot (b \cdot c) $

  • 存在幺元 $ e $,对于所有 $a \in S$,有 $ a \cdot e = e\cdot a = a $

构造函数和相关方法

segtree<S, op, e> seg(int n)
segtree<S, op, e> seg(vector<S> v)
  • S 是元素的类型,比如根据 vector<long long> a 来建立一棵线段树
    那么应该声明为 segtree<long long, op, e>

  • op 对应线段树节点的 pull 方法,S op(S a, S b)
    区间最小值为例

int op(int a, int b) {
  return min(a, b);
}
  • e 为幺元或者说是单位元S e(),同样以区间最小值为例
int e() {
  return (int)(1e9);
}

set, get

void seg.set(int p, S x)

对应单点修改,执行 $ a[p] = x $ 修改操作,复杂度 $ O(\log n) $

S seg.get(int p)

返回 $a[p]$ 的值

prod

S seg.prod(int l, int r)

对应线段树区间查询,注意是 $ [l, r) $ 的查询结果

返回 op(a[l], a[l+1], ..., a[r-1]) 的值
这里的 op 可以是区间加,也可以是区间乘,或者最大,最小值,gcd 等等

特别地,如果 $ l = r $,返回的是幺元 e()

复杂度是 $ O(\log n) $

all_prod

S seg.all_prod()

返回 op(a[0], ..., a[n - 1]),特别地,如果 $ n = 0 $,返回 e()

注意到,实际上建线段树的时候,我们经常是取序列下标 $ [1, n] $
这个时候我们需要让 $ a[0] = e() $ 即可

复杂度是 $ O(1) $

max_right

注意线段树二分一般满足条件的区间都是 $[l, r) $,左闭右开

(1) int seg.max_right<f>(int l)
(2) int seg.max_right<F>(int l, F f)

对应线段树上二分操作,比如给定操作 (l, r, d)
查询$a_{l}, a_{l+1}\cdots, a_r$ 区间中 $ \geqslant d $ 的第一个数下标

其中 f 是一个函数对象,必须定义

bool f(S x)
// 特别地,f(e()) = true

函数的返回值是 r,是第一个不符合 f 条件的下标位置

  • f( op(a[l], a[l+1], ..., a[r-1]) ) = true ,但是
    f( op(a[l], a[l+1], ..., a[r-1], a[r]) ) = false

  • 如果一整段都符合,那么返回 r = n,如果只有一个数符合,从 a[l+1]... 开始都不符合,那么返回 r = l

举个例子,我们要找到从下标 1 开始,最后一个满足 $ (a_1 + \cdots a_r) < 20 $ 的位置 r,可以这么来

int op(int a, int b) {
    return a + b;
}
int e() {
    return 0;
}
bool f(int x) {
    return x < 20;
}
// a = {1, 4, 5, 7, 10, 100}
segtree<int, op, e> seg({1, 4, 5, 7, 10, 100})
cout << seg.max_right<f>(1)
// 输出 4

程序返回 4,此时 a[4] = 10a[1] + ... + a[3] = 16 < 20
但是 16 + a[4] > 20 了,第一个不满足的下标就是 4

min_left

(1) int seg.min_left<f>(int r)
(2) int seg.min_left<F>(int r, F f)

类似地,同样必须定义一个函数对象

bool f(S x)
// 特别地,f(e()) = true

函数的返回值是一个下标 l,其中

  • f( op(a[l], a[l+1], ..., a[r-1]) ) = true,但是
    f( op(a[l-1], a[l], ..., a[r-1]) ) = false

  • 如果一整段都满足,返回 l = 0,没有一段满足,返回 l = r

单点修改的例子

给定一个序列 $$ a_l,\cdots, a_r $$,支持以下操作

  • 修改 a[x] = d
  • 查询 [l, r] 的最大子段和

算法分析

最大子段和是一个经典问题,执行区间合并 op 操作的时候
我们需要维护最大子段和 mss,前缀最大值 mpre,后缀最大值 msuf
设左儿子为 l,右儿子为 r

  • mss = max(l.mss, r.mss, l.msuf + r.mpre)
    其中 l.msuf + r.mpre 表示最大子段和横跨左右两个区间
  • 下面考虑 msufmpre 如何维护,以 msuf 为例
    msuf = max(r.msuf, r.sum + l.msuf)

什么意思呢?就是一个区间的后缀最大值,要么就只取右半边的后缀最大值
要么就是右半边一整段都要,再加上左区间的后缀最大值,mpre 同理

实例化代码如下

ll inf = 2e9;

struct S {
    ll sum, mss, mpre, msuf;
};

S op(S a, S b) {
    S res;
    res.sum = a.sum + b.sum;
    res.mpre = max(a.mpre, a.sum + b.mpre);
    res.msuf = max(b.msuf, b.sum + a.msuf);
    res.mss = max( {a.mss, b.mss, a.msuf + b.mpre} );
    return res;
}

S e() {
    return S{ 0, -inf, -inf, -inf };
}

int main() {
    vector<S> a(n, S{0, 0, 0, 0});
    for (int i = 0; i < n; i++) scanf("%lld", &a[i].sum);
    for (int i = 0; i < n; i++) {
        a[i].mss = a[i].mpre = a[i].msuf = a[i].sum;
    }

    segtree<S, op, e> seg(a);

    while (q--) {
        // ... 其他代码
        if (op == 1) {
            seg.set(x, S{d, d, d, d});
        }
        else {
            auto res = seg.prod(l, r+1);
        }
    }
}

源码如下

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
// constexpr int bsf_constexpr(unsigned int n) {
//     int x = 0;
//     while (!(n & (1 << x))) x++;
//     return x;
// }

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder
// segtree finished

using namespace atcoder;



题目大意

给你 $n$ 个复读机,每个复读机能复读一个值 $a_i$,下面你可以将任意一个复读机 $i$ 的幅度值,改成第 $b_i$ 个复读机的复读值

即 $a_i \leftarrow a_{b_i}$

下面问最少修改几次,能够把所有复读机复读值都改成一样的

算法分析

本题首先有一个性质,复读机复读值的改变,相当于在一个置换(排列) 中,令 $(i \to b_i \to b(b_i) \to \cdots)$

相当于一个有向图,并且每个点的出度都是 $1$

一个很重要的性质

有向图中,如果每个点的出度都是 $1$,那么这样的图叫 Functional Graph
这个 Functional Graph 的性质如下

  • 它有 $k$ 个连通分量 $C_1, C_2, \cdots C_k$,并且每一个连通分量都有且仅有一个简单环

那么有了这个性质之后,这个题目就可以做了

  • 不难发现,复读机改来改去,一定会形成若干个连通分量,每个连通分量最后都会在一个环上绕

  • 可以用 tarjan 或者其他算法,找到每个连通分量中的环,将每个环用 $[st, ed]$ 表示起点和终点

  • 最后沿着起点到终点,把每一个环上所有点的 $a$ 的值存下来,去重之后,对这些 $a$ 值取一个交集
    只有所有环都出现过的 $a$ 值,才有可能成为复读机最后复读的那个数

  • 那到底是哪个数呢?贪心地想,一定是需要改成出现次数最多的那个 $a$ 值,不妨设为 $tar$
    最后扫描一下序列,和 $tar$ 不同的,就令 $ans++$,最后 $ans$ 就是答案

typedef pair<int, int> PII;
typedef array<int, 3> Arr;

int main() {
    //freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;
    while (cas--) {
        int n;
        scanf("%d", &n);
        vector<int> a(n+1, 0), to(n+1, 0);
        // vector<vector<int> > G(n+1, vector<int>());

        unordered_map<int, int> show;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]), show[a[i]] += 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &to[i]);

            //G[i].push_back(to[i]);
        }

        int clk = 0;
        vector<int> dfn(n+1, 0), low(n+1, 0), ins(n+1, 0);
        stack<int> stk;

        vector<PII> cyc;
        int cnt = 0;
        auto tarjan = [&](auto self, int u) -> void {
            dfn[u] = low[u] = ++clk;
            stk.push(u), ins[u] = 1;

            auto v = to[u];
            {
                if (!dfn[v]) {
                    self(self, v);
                    low[u] = min(low[u], low[v]);
                }
                else if (ins[v]) {
                    low[u] = min(low[u], low[v]);
                    cyc.push_back(PII(u, v));
                }
            }

            if (dfn[u] == low[u]) {
                int v;
                do {
                    v = stk.top(), stk.pop(), ins[v] = 0;
                } while (v != u);
            }
        };

        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) tarjan(tarjan, i);
        }

        vector<vector<int> > gcyc(n+1, vector<int>());
        int k = 0;
        for (auto [st, ed] : cyc) {
            int u = ed;
            while (u != st) {
                gcyc[k].push_back(a[u]), u = to[u];
            }
            gcyc[k].push_back(a[st]);

            k += 1;
        }

        for (int i = 0; i < k; i++) {
            sort(gcyc[i].begin(), gcyc[i].end());
            gcyc[i].erase(unique(gcyc[i].begin(), gcyc[i].end()), gcyc[i].end());
        }

        unordered_map<int, int> nums;
        for (int i = 0; i < k; i++) {
            for (auto x : gcyc[i]) nums[x] += 1;
        }

        vector<int> can;
        for (int i = 0; i < k; i++) for (auto x : gcyc[i]) {
            if (nums[x] == k) can.push_back(x);
        }

        if (can.size() == 0) {
            puts("-1");
            continue;
        }

        int mx = -2e9, tar = -1;
        for (auto x : can) {
            if (chmax(mx, show[x])) tar = x;
        } 

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] != tar) ans += 1;
        }

        printf("%d\n", ans);
    }

}



题目大意

给你一个合法括号字符串,但是挖掉其中的一些 ) 或者 ( 字符,替换成 ?
现在给你一个挖掉的合法括号字符串,想要将其还原成原先的括号字符串,问这样的方案是不是唯一的

算法分析

括号字符串有一些常见的技巧和结论,相似的题目有
leetcode 2116. 判断一个括号字符串是否有效

那么这些题目中,都用到了一个很重要的结论,假设串的长度是 $n$

  • 如果一个串是合法括号串,那么它一定有 $n/2$ 个 ( 和 $n/2$ 个 )

  • 如果串的某些位置的字符可以变化,某些位置的字符不能变化,可以预处理出不能变化的 () 的数量
    不妨记为 $cntl, cntr$,那么对于可以变化的位置,我们需要变出 $needl$ 个 ( 和 $needr$ 个 )
    很显然 $needl = n/2 - cntl, \quad needr = n/2 - cntr$

  • 一种最优方案是,对于每一个可以变化的位置,将其存放到 $pos$ 中
    我们应该在 $pos$ 中最前面的位置替换成 $needl$ 个 (
    在 $pos$ 中最后面的位置替换成 $needr$ 个 )
    如果按照这种方案构造出来的串都不是合法括号串,那么其他情况不论怎么改,都不可能有合法括号串

结论 $1, 2$ 很显然,下面证明结论 $3$

证明
构造一个数组 $a[n]$,对于一个括号串的 $i$ 位置,如果 $str_i = ($,那么就令 $a[i] = 1$
如果 $str_i = ?$ 令 $a[i] = 0$,如果 $str_i = )$,那么令 $a[i] = -1$

记 $a[i]$ 的前缀和是 $S[i]$
那么一个串是合法括号串的条件,当且仅当 $S[n] = 0$,并且对于 $i \in [1, n-1]$ 的每一个位置
均有 $S[i] \geqslant 0$

那么现在问题转换成,你可以将 $a[i] = 0$ 的位置,变成 $+1$ 或者 $-1$,其中执行 $+1$ 操作恰好 $needl$ 次
执行 $-1$ 操作恰好 $needr$ 次,使得序列是合法括号序列

贪心策略是,对于一个很靠前的位置 $l$,令 $a_l \leftarrow a_l - 1$ 是不划算的
这样可能会使得前缀和减小,实际上,$a_i -= 1$ 会导致 $[i+1\cdots n]$ 所有位置的前缀和 $S$ 都 $-1$
那么就有可能出现 $S_j = 0$ 然后减掉 $1$ 变成负数,形成不合法的括号序列

相反,我们既然需要在 $needl$ 个位置 $+1$,我们让越靠前的位置 $a[i]+=1$
这样就能够令 $[i+1, n]$ 这些位置的前缀和尽量大,如果这样处理,在 $[i+1, n]$ 的某些位置还会出现 $S < 0$
那么无论怎么改也不可能出现合法括号序列了

结论 $3$ 证明完毕

有了这些结论之后,这个问题就很好想了

  • 预处理出所有问号的位置,并且按上述方式,在尽量靠前的地方放 $needl$ 个 (
    靠后的地方放 $needr$ 个 )

  • 因为题目保证了给出的序列一定能构造出合法的括号序列,所以如果有解且唯一
    那么按上述方式构造出来的解就是唯一解,也是最优解

  • 如果解不唯一,那么我们尝试看看次优解是什么
    经过上面的分析,我们还是应该在尽可能靠前的位置放 (,在尽可能靠后的位置放 )
    那么次优解就是,在最优解的基础上,最后一个 ( 位置和第一个 ) 位置交换

  • 于是我们检查一下次优解是不是一个合法括号序列,如果不是,那么答案唯一
    如果是,那么答案不唯一

int main() {
    freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;
    while (cas--) {
        string str;
        cin >> str;
        int n = str.size();

        int cntl = 0, cntr = 0;
        for (int i = 0; i < n; i++) {
            if (str[i] == '(') cntl += 1;
            if (str[i] == ')') cntr += 1;
        }

        int needl = n/2 - cntl, needr = n/2 - cntr;
        if (needl == 0 || needr == 0) {
            puts("YES");
            continue;
        }

        vector<int> posl, posr;

        for (int i = 0; i < n; i++) {
            if (str[i] != '?') continue;

            if (posl.size() < needl) {
                str[i] = '(', posl.push_back(i);
            }
            else {
                str[i] = ')', posr.push_back(i);
            }
        }

        auto check = [&]() -> bool {
            stack<int> stk;
            for (int i = 0; i < n; i++) {
                auto c = str[i];

                if (c == '(') stk.push(i);
                else {
                    if (stk.size() == 0) return false;
                    stk.pop();
                }
            }
            return true;
        };

        swap(str[posl.back()], str[posr[0]]);

        if (check()) puts("NO");
        else puts("YES");
    }
}

类似地leetcode 2116. 判断一个括号字符串是否有效
代码也放上

class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n = s.size();

        auto check = [&](const string &str) -> bool {
            stack<int> stk;
            for (auto c : str) {
                if (c == '(') stk.push(c);
                else {
                    if (stk.empty()) return false;
                    stk.pop();
                }
            }
            return true;
        };

        if (n & 1) return false;

        int cntl = 0, cntr = 0;

        int can = 0;
        for (int i = 0; i < n; i++) {
            if (locked[i] == '0') {
                can += 1;
                continue;
            }

            if (s[i] == '(') cntl += 1;
            else cntr += 1;
        }

        int needl = n/2 - cntl, needr = n/2 - cntr;

        if (can < needl || can < needr) {
            return false;
        }
        int nowl = 0, nowr = 0;

        for (int i = 0; i < n; i++) {
            if (locked[i] == '1') continue;

            if (nowl < needl) s[i] = '(', nowl += 1;
            else if (nowr < needr) s[i] = ')', nowr += 1;
        }

        bool ans = check(s);
        return ans;
    }
};



题目大意
你有一个排列 $a$,现在你可以根据 $a$ 得到数组 $b$,其中 $b_i = \displaystyle \left \lfloor \frac{i}{a_i} \right \rfloor$

现在你忘了排列 $a$ 是啥,给你一个数组 $b$,要求从数组 $b$ 构造出数组 $a$

原问题可以转换成为,已知 $i, b_i$,构造出 $a_i$ 满足

$\displaystyle \frac{i}{b_i+1} < a_i \leqslant \frac{i}{b_i}$,不妨记 $L(i) = \displaystyle \frac{i}{b_i + 1} + 1, R(i) = \frac{i}{b_i}$

下面问题转换成
给你 $n$ 个数,第 $i$ 个数的取值区间是 $[L(i), R(i)]$,要求你在每一个区间内选一个数来构造排列
其中要求,所选的数不能重合,这是贪心算法中很典型的活动选择问题

在活动选择问题中,我们是这样执行贪心策略的
对所有区间按照右端点排序,然后依次检查每一个区间
对于每个区间,我们选择最小的,并且未被选过的数,那么这个问题也类似

这个问题与区间选择问题不同的是,可能多个 $a(i_1), a(i_2), \cdots$ 有着相同的左端点
可以先打表处理 $\text{has}(x) = {i_1, i_2, \cdots}$,表示这些 $i$ 都以 $x$ 作为值域区间的左端点

然后我们遍历 $\textbf{for} \ \forall x \in [1\cdots n]$
对于 $\text{has}(x)$ 中的 ${i_1, i_2, \cdots }$,根据活动选择问题中的分析
这些 $i$ 我们理论上都可以赋值成 $a_i = x$,但我们应该取 $R(i)$ 尽量小的那个 $i$ 赋值成 $x$

算法实现上,用一个二元组 $(R(i), i)$ 来表示
那么我们应该把 $x$ 值,赋给尽量小的 $R(i)$ 所对应的那个 $i$
将二元组放入 $\text{set}$ 中,然后将 $\text{set}$ 最开头那个元素对应的 $i$ 赋值成 $x$
赋值完成后就将其删除,这样就保证了每个元素只会被赋值一次

typedef pair<int, int> PII;
int main() {
    freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;
    while (cas--) {
        int n;
        cin >> n;
        vector<int> b(n+1, 0);
        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

        vector<int> L(n+1, 0), R(n+1, 0);
        map<int, vector<int> > has;
        for (int i = 1; i <= n; i++) {
            L[i] = i / (b[i]+1) + 1;
            R[i] = b[i] == 0 ? n : i / b[i];
            has[L[i]].push_back(i);
        }

        set<PII> st;
        vector<int> ans(n+1, 0);
        for (int x = 1; x <= n; x++) {
            for (auto i : has[x]) {
                st.insert(PII(R[i], i));
            }
            if (ans[st.begin()->second] == 0) {
                ans[st.begin()->second] = x, st.erase(st.begin());
            }
        }

        for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
        printf("\n");
    }
}



题目大意
给你一个数组 $a[1, n]$,可能有重复元素,每一个元素的值都在 $[1, m]$ 之间
接下来你可以
在 $a$ 中选出一个元素 $x$,然后对 $x$ 进行分解,$x = p\cdot q, \ (p, q > 1)$
然后把 $x$ 从 $a$ 中删除,再把 $p, q$ 加入集合 $a$ 中
问经过若干次这样的操作之后,数组的 $\max(a_i) - \min(a_i)$ 最小是多少

先来看一个经典问题
给你一个数组,要求你求一个区间 $[l, r]$,使得这个区间中 $\max(a_i) - \min(a_i)$ 最大或最小

这个问题我们一般是枚举最小值 $x$,单调栈求出左边第一个 $> x$ 的元素位置 $l$
以及右边第一个 $> x$ 的元素位置 $r$,那么 $[l+1, r-1]$ 区间的最小值都是 $x$

接下来只需要用 $\text{ST}$ 表或者是线段树求出 $[l+1, r-1]$ 的最大值 $maxv$ 即可
然后用 $maxv - x$ 来更新全局的 $ans$,即可在 $O(n \log n)$ 的复杂度内完成问题求解

本题也可以类似考虑
枚举 $i$ 作为序列最小元素 $minv$ 时候的情形,问题等价于
对于每一个 $i$,$i$ 可以由 $x \in [i\cdot i, \ i \cdot(i+1), \ i \cdot (i+2) \cdots ]$ 分解而来

$i$ 作为 $x$ 分解得到的最小的因子,我们要在 $x$ 分解出来的,并且 $\geqslant i$ 的因子中
找到尽量小的那个因子,记这个尽量小的因子是 $dp_i(x)$

尽量小的,并且比 $i$ 大的因子记为 $res$

这样对于每一个 $x$ 有 $2$ 种决策

  • $x$ 分解出一个 $i$ 来,不往下继续分解了,$res = dp_i(x)$

  • 对 $x/i$ 继续往下分解,枚举 $x/i$ 的分解情况
    $\textbf{for} \ \forall j \mid (x/i)$,$j$ 作为 $x/i$ 的因子,必须满足
    $\textbf{(1)}\quad j > i, \ j = [i, i+1, \cdots]$
    $\textbf{(2)}\quad j$ 是 $x/i$ 分解出来的最小因子

这样就有转移

$\displaystyle dp_i(x) = \min(dp_i(x), \forall j \min_{j} dp_j(x/i)), j$ 满足上述两个条件

那么这个问题很容易用 $O(n^2)$ 枚举求解,一边求解的时候一边用 $dp_i(x) - i$ 更新答案即可
下面考虑如何优化

注意到我们这里用 $dp_j(x’)$ 来更新 $dp_i(x)$,其中 $j \geqslant i$
如果我们 $j$ 从大往小去遍历,相应的 $dp_{j+1}(x)$ 就可以实时维护
换句话说,当 $j+1 \to j$ 的时候,$dp_{j+1}(x)$ 的值实际上是维护了 $\left< dp_{j+1}(x), dp_{j+2}(x), \cdots \right>$

由此,从大往小去遍历 $i$,上面的式子就可以实时维护了
具体来说用旧的 $dp(x/i)$ 来更新当前的 $dp(x)$

那最后一个问题就是如何计算答案,可以用一个 $\textbf{set}$ 维护 $dp$ 值,一开始所有数 $dp(x) = x$
将其都放入 $\text{set}$ 中
对于 $\textbf{for} \ \forall i \in [maxv \to 1]$
执行 $dp(x) = \min (dp(x), dp(x/i))$ 的时候,我们要这样做
(1)将原来的 $dp(x)$ 从 $\text{set}$ 中删除
(2)更新 $dp(x) = \min(dp(x), dp(x/i))$
(3)在 $\text{set}$ 中插入新的 $dp$ 值

当遍历 $i \leqslant minv$,$minv$ 是原序列的最小值
我们就可以用 $\text{set 中的最大值} - i$ 来更新答案了


typedef pair<int, int> PII;

int main() {
    freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;
    while (cas--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n+1, 0);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        ll mn = m+1, mx = 0;
        for (int i = 1; i <= n; i++) {
            chmax(mx, 1LL*a[i]), chmin(mn, 1LL *a[i]);
        }

        ll ans = mx - mn;
        vector<ll> dp(mx+1, 0);
        for (int i = 1; i <= mx; i++) dp[i] = i;

        vector<int> vis(mx+1, 0), exist(mx+1, 0);
        for (int i = 1; i <= n; i++) {
            auto x = a[i];
            vis[x] = 1, exist[x] = 1;
        }

        ll ptr = mx;
        for (ll i = mx; i >= 1; i--) {
            for (ll x = i*i; x <= mx; x += i) {
                if (vis[x]) exist[dp[x]] -= 1;
                dp[x] = min(dp[x], dp[x/i]);
                if (vis[x]) exist[dp[x]] += 1; 
            }

            while (!exist[ptr]) ptr--;

            if (i <= mn) chmin(ans, ptr-i);
        }

        cout << ans << endl;
    }
}



题目大意
给你一个数组 $a[1\cdots n]$,每一次操作,如果 $a_i \neq a_{i+1}$,可以将 $a_i, a_{i+1}$ 都删掉
删掉之后剩下的数拼接起来
经过若干次这样操作之后,最后要使得数组中所有元素都相同
那么最后的数组最大长度是多少

思路分析
由于操作之后数组中所有元素都相同,$n \leqslant 5000$,所以可以枚举操作完成后,数组中相同元素的值 $x$
一开始可以对 $x$ 出现的所有位置打表,记 $x$ 出现的第 $i$ 个位置是 $\displaystyle f_x(i)$
只考虑 $x$ 出现的位置,从 $i-1 \to i$

对于区间 $[f_x(i-1)\cdots f_x(i)]$,如果中间的数 $[f_x(i-1)+1, f_x(i)-1]$ 能全部消去
那么就存在转移 $f_x(i) = f_x(i-1) + 1$
其中 $f_x(i)$ 表示第 $i$ 个 $x$ 这个位置,得到的数组的最大长度

这样就启发我们用 $dp$ 来实现
$dp(i)$ 表示 $i$ 位置的这个数最终保留下来,并且作为序列结尾,能得到的序列最大长度
那么存在 $dp(i) = \max(dp(j) + 1) \quad (a_j = a_i, \ 1 \leqslant j \leqslant i-1)$ 的转移
当且仅当 $[j+1, i-1]$ 中的数可以消去

要想保留 $a_i$,那么 $dp$ 的起点一定是找到第一个 $x = a_i$ 所在的位置 $s$
令 $dp(s) = 1$,然后递推
一开始的时候,所有点的 $dp$ 值都是 $0$,先预处理一下
如果 $[1\cdots i-1]$ 的前缀可以消去,那么 $i$ 就可以作为 $dp$ 的起点,$dp(i) = 1$
接着按上面的方法递推就可以

接下来的难点就是,什么时候 $[l, r]$ 中的元素可以全部消去?不妨设 $[l, r]$ 中的元素个数为 $n$

  • $n$ 必须是偶数,这根据题意很容易发现

  • 实际上消去的充要条件是,对 $[l, r]$ 中的每一个数 $x$,都能找到一个 $y \neq x$ 与它匹配
    对于出现次数最大的数 $x$
    $x$ 如果出现次数 $> n/2$,必然有某个 $x$ 找不到匹配,否则一定是可以的

证明如下,如果出现次数最多的数 $x$ 出现的次数都 $\leqslant n/2$,那么最坏的情况
就是序列一段都是 $x$,最前面的 $x$ 能消去,那么一整段都可以消去
这是可能的,因为我们可以贪心地考虑 $[2\cdots, n/2]$
这些 $x$ 从后往前依次和 $[n/2+1 \cdots n]$ 这些 $y \neq x$ 配对删除
再来看看充分性
如果有一个数 $x$ 出现次数 $k > n/2$,那么其他元素的个数是 $n - k$
因为其他元素都要被删除,所以还剩下无法匹配的 $x$ 个数是 $n - 2(n-k) > 0$
这显然是不符合全部删除的要求的

最后计算答案的时候,因为每一个位置 $i$ 都可能作为序列的结尾
根据之前的分析,$dp(i)$ 是 $i$ 这个位置保留下来并且作为序列结尾,能够得到的最大长度
如果 $[i+1, n]$ 这一段能够完全删除,那么就可以对所有这样的 $dp(i)$ 取一个 $\max$ 就是答案

int main() {
    //freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;
    while (cas--) {
        int n;
        cin >> n;
        vector<int> a(n+1, 0);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        vector<vector<int> > candel(n+1, vector<int>(n+1, 0));
        for (int i = 1; i <= n; i++) {
            int mx = 0;
            vector<int> cnt(n+1, 0);

            for (int j = i; j <= n; j++) {
                cnt[a[j]]++;
                chmax(mx, cnt[a[j]]);
                if ((j-i+1) % 2 == 0 && mx <= (j-i+1)/2) candel[i][j] = 1;
            }
        }

        vector<int> dp(n+1, 0);
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (candel[1][i-1]) dp[i] = 1;
            else dp[i] = -0x3f;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (a[j] != a[i]) continue;
                if (j == i-1 || candel[j+1][i-1]) chmax(dp[i], dp[j] + 1);
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) if (i == n || candel[i+1][n]) chmax(ans, dp[i]);
        cout << ans << endl;
    }
}



题目大意
给你一个序列 $a$,$a$ 是一个 $[0\to n-1]$ 的排列
问能够造出多少种序列 $b$,其中 $b$ 也是一个 $[0 \to n-1]$ 的排列
并且必须满足,$b$ 所有的子区间 $[l, r]$
$\text{mex}(b_l\cdots, b_r) = \text{mex}(a_l, \cdots, a_r)$

算法分析
因为 $b$ 是一个排列,所以 $b$ 的所有子区间的 $\text{mex}$ 值一定会取遍 ${0, 1, \cdots, n-1, n}$
于是我们可以一个一个数考虑,对于数 $x \in [0, n-1]$,考虑它有几个位置可以放置?
最后把答案都乘起来就可以

不妨设当前正在考虑的数为 $x$
并且使得 $[0\cdots x-1]$ 这些数都出现过的最小区间是 $[l, r]$,我们有一些性质

  • $[l, r]$ 中的所有子区间(不包括 $[l, r]$)的 $\text{mex}$ 值只能在 ${0,1, \cdots, x-1}$ 中取
    并且除了 ${0, 1, \cdots, x-1}$ 这些数所在的位置之外,剩下的数都 $> x-1$
    只要 ${0, 1, \cdots, x-1}$ 这些数的位置不变,剩下的数换成任意一个 $> x-1$ 的数
    所有子区间的 $\text{mex}$ 值都不会改变

  • ${0, 1, \cdots, x-1}$ 这些位置呢?实际上这是一个子问题
    考虑 $[0\cdots x-2]$ 所有数都出现的最小子区间 $[l’, r’]$,如上分析

这样就启发我们从 $x \in [0 \to n-1]$ 递推考虑
不妨设当前正在考虑的数是 $x$,首先必须找到最小的满足 $[0\cdots x-1]$ 都出现的区间 $[l, r]$

  • $x$ 在 $[l, r]$ 区间外面,不妨设它的位置是 $p(x)$,$p(x) > r$
    那么此时 $b$ 中 $x$ 的位置不能动
    因为 $\text{mex}([r+1, p(x)-1]) = x$,如果将 $x$ 移动到 $\text{p}(x) - 1$
    那么 $\text{mex}([r+1, p(x)-1]) = x+1 \neq x$,不符合条件

  • $x$ 在 $[l, r]$ 区间中,$l \leqslant p(x) \leqslant r$
    经过我们上面的分析,$x > x-1$
    所以 $x$ 可以放置在除了 ${0, 1, \cdots, x-1}$ 所在位置之外的任意一个位置
    $x$ 放置位置的方案数为 $(r-l+1 - x)$

代码说明

mint 使用atcoder中的 mint 模数类
int main() {
    freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;
    while (cas--) {
        int n;
        cin >> n;

        vector<int> a(n, 0);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);

        map<int, int> pos;
        for (int i = 0; i < n; i++) pos[a[i]] = i;

        int l = pos[0], r = pos[0];
        mint res = 1;
        for (int x = 1; x < n; x++) {
            if (l <= pos[x] && pos[x] <= r) res *= mint(r-l+1 - x);
            else {
                chmin(l, pos[x]), chmax(r, pos[x]);
            }
        }

        cout << res.x << endl;
    }
}



很迷,赛中用 vector 被卡了,一度以为算法出了问题,整半天都用dfs序 + 线段树硬是没搞出来
赛后用了普通的暴力 dfs 就过了,只不过换了一个 unordered_set,很迷

算法分析

  • 首先把图建出来,然后枚举删除哪一条边,不妨设删除了边 $(x, y)$
    那么这个时候 $x, y$ 分别形成独立的树,可以 $dfs(x), dfs(y)$ 分别求出以 $x, y$ 为根的子树
    所有点权值的异或和,不妨设为 $(sx, sy)$

  • 然后呢,去遍历 $x$ 的子树,再 $dfs$ 一遍,这样对于 $x$ 的子树,有如下情况
    $x$ 的某个子树 $u$,$u$ 的整棵子树的异或和,可以一边 $dfs$ 的时候一边返回
    不妨设为 $t$,这样原来的图就被分为三个部分 $(sy, t, sx \oplus t)$,按题意更新全局的最小值即可
    $y$ 的子树同理

#pragma GCC optimize(2)
const int maxn = 1000 + 10;
class Solution {
public:
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        int m = edges.size(), n = nums.size();
        unordered_set<int> G[maxn];

        function<int(int, int)> dfs = [&](int x, int fa) {
            int res = nums[x];
            for (auto y : G[x]) {
                if (y == fa) continue;
                res ^= dfs(y, x);
            }
            return res;
        };

        int ans = 1e9;

        function<int(int, int, const int, const int, const int)> sub = [&](int x, int fa, const int root, const int sx, const int sy) {
            int t = nums[x];
            for (auto y : G[x]) {
                if (y == fa) continue;
                t ^= sub(y, x, root, sx, sy);
            }

            if (x != root) {
                int mx = max( {sy, sx ^ t, t} ), mn = min( {sy, sx ^ t, t} );
                ans = min(ans, mx - mn);
            } 

            return t;
        };

        for (int i = 0; i < m; i++) {
            int x = edges[i][0], y = edges[i][1];
            G[x].insert(y), G[y].insert(x);
        }


        for (int i = 0; i < m; i++) {
            // delete edges[i]
            int x = edges[i][0], y = edges[i][1];
            G[x].erase(y), G[y].erase(x);

            int sx = dfs(x, -1), sy = dfs(y, -1);
            int tot = sx ^ sy;

            // (sy, sub(sx), sx^sub(sx)), (sx, sub(sy), sy^sub(sy))
            // array<int, 3> help;
            sub(x, -1, x, sx, sy), sub(y, -1, y, sy, sx);

            G[x].insert(y), G[y].insert(x);
        }
        return ans;
    }
};



算法分析

本例中需要支持如下操作,在 $n \times m$ 的方阵中,如果让 $(x, y)$ 出方阵,那么

  • 找到标号第 $x$ 大的行,并且在该行中找到第 $y$ 大的列,将对应的元素 $(x, y)$ 取出
    然后把该行中 $[y+1\cdots m]$ 整体往前挪一位

  • 然后操作第 $m$ 列,将第 $m$ 列 $[x+1\cdots n]$ 整体往上挪一位

  • 最后把取出来的元素插入 $(n, m)$ 处

注意到我们需要对 $n$ 行,以及第 $m$ 列求前缀第 $k$ 大
可以考虑一开始建 $n+1$ 棵线段树,其中每一棵线段树初始只有一个根节点
这样第 $[1\cdots n]$ 棵线段树维护 $[1 \to n]$ 行,第 $n+1$ 棵线段树维护第 $m$ 列

将线段树写成动态开点,这样就可以尝试维护操作了,维护区间内被删除了多少个数 $cnt$

  • 对于删除 $(x, y)$,就是在第 $x$ 棵线段树 $tr(x)$ 中找到第 $y$ 大的数 $p$,然后返回 $p$
    如果要对应到方阵中的编号,那么就是 $id = (x-1)\cdot m + p$
    然后删除这个点,采用懒惰删除的方法,对线段树这个点标记为删除,即 $u.\text{cnt} + 1$

  • 值得注意的是,懒惰删除的时候,和一般线段树不一样,我们 $\text{pull}(u)$ 的时候
    因为是动态开点的,$u$ 的左子树或者右子树可能不存在,要加判一下子树存在
    以左子树为例,如果 $u.l \neq \text{null}$,那么直接 $u.\text{cnt} += u.l.\text{cnt}$
    否则的话左子树不存在,也就是说我们并没有修改过左子树对应的区间,$u.\text{cnt} += 0$

  • 修改的时候,比如要出列第 $y$ 个人,只需要把 $root \to y$ 路径上的点都开出来就可以
    唯一需要注意的是,递归子树的时候,如果子树是 $\textbf{null}$,那么要先 $\textbf{new}$ 出来节点然后递归

  • 接着考虑查询第 $k$ 大,同样需注意,递归子树遇到 $\textbf{null}$ 要先将其 $\textbf{new}$ 出来
    假设当前递归到 $(u, l, r)$,那么左子树中的元素个数是 $tot = mid - l + 1$
    如果左子树非空,那么 $tot$ 还要扣除掉已经删除的元素,即 $tot -= u.l.\text{cnt}$
    否则,说明左子树对应的区间我们没有修改过,自然对应的 $\text{cnt} = 0$

  • 然后执行很常见的二分查找逻辑,如果 $k \leqslant tot$,那么在左子树查找第 $k$ 大
    否则去右子树找第 $k - tot$ 大

综上所述

  • 通过线段树维护,可以得到要出列的点编号,假设是 $id = (x-1) \cdot m + y$
    可以用一个 $\text{vector}$ 存储被取出的点,$\text{vector}[x] \leftarrow {y}$ 表示
    第 $x$ 棵线段树被删除点的情况就存储到 $\text{vector}[x]$ 中

  • 接着是查询第 $x$ 大的下标 $p$,如果是叶子节点,就直接返回 $p = l$,否则二分查询左右子树

  • 接下来有一些坑点,注意到对 $x$ 行修改,得到的前 $y$ 大 $\in [1, m-1]$
    最后一列我们是单独拿出来处理的,如果 $p \geqslant m$,那么查询到的这个人是
    “向左看齐” 之后由最后一列第 $x$ 大填补空缺补充上来的

  • 由此对 $(x, y)$ 出列操作,还需要额外维护最后一列填补空缺的人的编号
    即在第 $n+1$ 棵线段树中查找第 $x$ 大,此时这个编号的人不需要出列,而是填补空缺

由此程序实现需要注意的

  • 对最后一列操作,即第 $n+1$ 棵线段树,维护两种情况

  • 第一种是 $solve(1)$
    这一列的第 $x$ 个人出列,此时 $\text{vector}[n+1] \leftarrow {x}$,这个人要重新插入到末尾

  • 另外一种是 $solve(0)$
    前 $m-1$ 列的人出队,假设说是 $(x, y)$,在第 $n+1$ 棵线段树找到第 $x$ 大之后
    这个人是要填补空缺的,不需要真正出列,不需要将其放在 $\text{vector}[n+1]$ 的末尾
    而是要放到 $\text{vector}[x]$ 的末尾

  • 对其他列操作,加入是 $(x, y)$,在第 $x$ 棵线段树中找到第 $y$ 大的编号 $id$,做两件事情
    第一是在将 $id$ 加入到第 $n+1$ 棵线段树对应的 $\text{vector}$ 末尾,即 $\text{vector}[n+1] \leftarrow {id}$
    第二就是填补空缺,在第 $n+1$ 棵线段树中找到第 $x$ 大的编号 $id2$,$\text{vector}[x] \leftarrow {id2}$

这样所有信息都维护好了

  • 如果对第 $m$ 列操作,查询第 $x$ 大的下标是 $p$,$p \leqslant n$ 直接返回 $p$
    否则是出列过之后又进来的,返回 $\text{vector}[n+1][p-n-1]$

  • 如果对让 $(x, y)$ 出列,$x \leqslant m-1$,那么同样查询第 $y$ 大的下标 $p$
    $p \leqslant m-1$ 直接返回,否则返回 $\text{vector}[x][p-m]$\

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <functional>
#include <bit>
#include <random>
#include <numeric>

using namespace std;
typedef long long ll;

#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define lowbit(i) (i & (-i))
#define fill_v(f, v) fill(f.begin(), f.end(), v)

template<class T> 
inline void debug_v(const vector<T> &vec) {
    printf("vec: ");
    for (auto u : vec) cout << u << " ";
    cout << endl;
}

template<class T>
inline int cntOne(const T x) {
    bitset<64> res(x);
    return res.count();
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

constexpr int P = 1e9 + 7;

int norm(int x) {
    if (x < 0) x += P;
    if (x >= P) x -= P;
    return x;
}

template<class T>
T power(T a, int b) {
    T res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res *= a;
        a *= a;
    }
    return res;
}

struct mint {
    int x;
    mint(int x = 0) : x(norm(x)) {}

    int val() const {
        return x;
    }
    mint operator-() const {
        return mint(norm(P-x));
    }
    mint &operator *= (const mint &rhs) {
        x = (ll)(x) * rhs.x % P;
        return *this;
    }
    mint &operator += (const mint &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    mint &operator -= (const mint &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    mint &operator /= (const mint &rhs) {
        return *this *= rhs.inv();
    }
    mint inv() const {
        assert(x != 0);
        return power(*this, P-2);
    }
    friend mint operator* (const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res *= rhs;
        return res;
    }
    friend mint operator+ (const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res += rhs;
        return res;
    }
    friend mint operator- (const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res -= rhs;
        return res;
    }
    friend mint operator/ (const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res /= rhs;
        return res;
    }
};

struct Int {
    static constexpr int B = 10;
    vector<int> X;
    int size() const {
        return (int)X.size();
    }

    Int(int x = 0) {
        while (x) {
            X.push_back(x % B), x /= B;
        }
    }

    Int(string str) {
        reverse(str.begin(), str.end());
        for (auto u : str) X.push_back(u-'0');
    }

    friend Int operator+ (const Int &lhs, const Int &rhs) {
        if (lhs.size() < rhs.size()) return rhs + lhs;
        Int res;

        int t = 0;
        for (int i = 0; i < lhs.size(); i++) {
            t += lhs.X[i];
            if (i < rhs.size()) t += rhs.X[i];
            res.X.push_back(t % B), t /= B;
        }
        if (t) res.X.push_back(t);
        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend Int operator- (const Int &lhs, const Int &rhs) {
        Int res;
        int t = 0;
        for (int i = 0; i < lhs.size(); i++) {
            t = lhs.X[i] - t;
            if (i < rhs.size()) t -= rhs.X[i];
            res.X.push_back((t + B) % B);

            if (t < 0) t = 1;
            else t = 0;
        }
        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend Int operator* (const Int &lhs, int b) {
        Int res;
        int t = 0;
        for (int i = 0; i < lhs.X.size() || t; i++) {
            if (i < lhs.X.size()) t += lhs.X[i] * b;
            res.X.push_back(t % B), t /= B;
        }
        return res;
    }

    friend Int operator/ (const Int &lhs, int b) {
        Int res;
        int r = 0;
        for (int i = lhs.X.size()-1; i >= 0; i--) {
            r = r * B + lhs.X[i];
            res.X.push_back(r / b), r %= b;
        }
        reverse(res.X.begin(), res.X.end());
        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend Int operator* (const Int &lhs, const Int &rhs) {
        Int res;
        res.X.resize(lhs.size() + rhs.size() + B);
        fill(res.X.begin(), res.X.end(), 0);

        for (int i = 0; i < lhs.size(); i++) {
            for (int j = 0; j < rhs.size(); j++) {
                res.X[i+j] += lhs.X[i] * rhs.X[j];
            }
        }
        for (int i = 0; i < res.X.size(); i++) {
            if (res.X[i] >= B) res.X[i+1] += res.X[i] / B, res.X[i] %= B;
        }

        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend Int operator/ (const Int& lhs, const Int &rhs) {
        int dv = lhs.size() - rhs.size();
        assert(dv >= 0);

        Int res;
        res.X.resize(dv+1);
        fill(res.X.begin(), res.X.end(), 0);

        // append suffix zero
        Int a = lhs, b = rhs;
        reverse(b.X.begin(), b.X.end());
        for (int i = 0; i < dv; i++) b.X.push_back(0);
        reverse(b.X.begin(), b.X.end());

        for (int i = 0; i <= dv; i++) {
            while (b < a) {
                a = a-b;
                res.X[dv-i]++;
            }
            b.X.erase(b.X.begin());
        }
        while (res.X.size() > 1 && res.X.back() == 0) res.X.pop_back();
        return res;
    }

    friend bool operator< (const Int &lhs, const Int &rhs) {
        if (lhs.size() < rhs.size()) return true;
        if (lhs.size() > rhs.size()) return false;

        if (vector<int>(lhs.X.rbegin(), lhs.X.rend()) <= vector<int>(rhs.X.rbegin(), rhs.X.rend())) return true;
        return false;
    }
    void out() {
        if (X.size() == 0) {
            puts("0");
            return;
        }
        reverse(X.begin(), X.end());
        for (auto x : X) printf("%d", x);
        printf("\n");
    }
};

Int max_int(const Int &A, const Int &B) {
    if (A < B) return B;
    else return A;
}

int get_root(int P) {
    function<vector<int>(int x)> divide = [&](int x) {
        vector<int> primes;
        for (int i = 2; i <= sqrt(x); i++) {
            if (x % i) continue;

            primes.push_back(i);
            while (x % i == 0) x /= i;
        }
        if (x > 1) primes.push_back(x);

        return primes;
    };

    vector<int> pr = divide(P-1);

    for (ll g = 2; g <= P-1; g++) {
        bool ok = true;

        for (auto p : pr) {
            if (ksm(g, (1LL * P-1)/p, P) == 1) {
                ok = false; break;
            }
        }

        if (ok) return g;
    }
    return -1;
}

namespace NTT {
    const int G = 3;

    vector<int> rev;
    void ntt(vector<mint> &a, int op) {
        int n = a.size();

        if ((int)rev.size() != n) {
            rev.resize(n);
            // int k = __builtin_ctz(n);
            //int k = countr_zero((unsigned int)n);
           int k = 0; 

            for (int i = 0; i < n; i++) {
                rev[i] = rev[i>>1] >> 1 | (i&1) << (k-1);
            }
        }

        for (int i = 0; i < n; i++) {
            if (rev[i] < i) swap(a[i], a[rev[i]]);
        }

        // swap
        for (int mid = 1; mid < n; mid <<= 1) {
            mint gn = power(mint(G), (P - 1) / (mid << 1));
            if (op == -1) gn = gn.inv();

            for (int i = 0; i < n; i += mid * 2) {
                mint gnk = 1;

                for (int j = 0; j < mid; j++) {
                    mint u = a[i+j], v = gnk * a[i+mid+j];
                    a[i+j] = u + v, a[i+mid+j] = u - v;
                    gnk = gnk * gn;
                }
            }
        }

        if (op == -1) {
            mint inv = mint((int)a.size()).inv();
            for (int i = 0; i < n; i++) {
                a[i] *= inv;
            }
        }
    }

    void dft(vector<mint> &a) {
        ntt(a, 1);
    }

    void idft(vector<mint> &a) {
        ntt(a, -1);
    }
};

struct Poly {
    vector<mint> a;
    Poly() {}
    Poly(const vector<mint> &a) : a(a) {}
    Poly(const initializer_list<mint> &a) : a(a) {}
    int size() const {
        return a.size();
    }
    void resize(int n) {
        a.resize(n);
    }

    mint operator[] (int idx) const {
        if (idx < 0 || idx >= size()) {
            return 0;
        }
        return a[idx];
    }
    mint& operator[] (int idx) {
        return a[idx];
    }

    Poly mulxk(int k) const {
        auto b = a;
        b.insert(b.begin(), k, 0);
        return Poly(b);
    }
    Poly modxk(int k) const {
        k = min(k, size());
        return Poly(vector<mint>(a.begin(), a.begin() + k));
    }
    Poly divxk(int k) const {
        if (size() <= k) {
            return Poly();
        }
        return Poly(vector<mint>(a.begin() + k, a.end()));
    }

    friend Poly operator+ (const Poly &a, const Poly &b) {
        vector<mint> res(max(a.size(), b.size()));
        for (int i = 0; i < (int)res.size(); i++) {
            res[i] = a[i] + b[i];
        }
        return Poly(res);
    }

    friend Poly operator- (const Poly &a, const Poly &b) {
        vector<mint> res(max(a.size(), b.size()));
        for (int i = 0; i < (int)res.size(); i++) {
            res[i] = a[i] - b[i];
        }
        return Poly(res);
    }

    friend Poly operator* (Poly a, Poly b) {
        using namespace NTT;

        if (a.size() == 0 || b.size() == 0) {
            return Poly();
        }

        int sz = 1, tot = a.size() + b.size() - 1;
        while (sz < tot) sz *= 2;

        a.a.resize(sz), b.a.resize(sz);
        dft(a.a), dft(b.a);

        for (int i = 0; i < sz; i++) {
            a.a[i] = a[i] * b[i];
        }

        idft(a.a);
        a.resize(tot);
        return a;
    }

    friend Poly operator* (Poly a, mint b) {
        for (int i = 0; i < (int)a.size(); i++) {
            a[i] *= b;
        }
        return a;
    }

    friend Poly operator* (mint a, Poly b) {
        for (int i = 0; i < (int)b.size(); i++) {
            b[i] *= a;
        }
        return b;
    }

    Poly &operator+= (Poly b) {
        return (*this) = (*this) + b;
    }
    Poly &operator-= (Poly b) {
        return (*this) = (*this) - b;
    }
    Poly &operator*= (Poly b) {
        return (*this) = (*this) * b;
    }

    Poly deriv() const {
        if (a.empty()) return Poly();

        vector<mint> res(size() - 1);
        for (int i = 0; i < size()-1; i++) {
            res[i] = (i + 1) * a[i + 1];
        }

        return Poly(res);
    }

    Poly integr() const {
        vector<mint> res(size() + 1);
        for (int i = 0; i < size(); i++) {
            res[i + 1] = a[i] / (i + 1);
        }
        return Poly(res);
    }
};

mt19937_64 mrand(random_device{}());
int rnd(int x) {
    return mrand() % x;
}

// ============================================================== //

struct info {
    info *l = nullptr, *r = nullptr;
    ll cnt;

    bool leaf() const {
        return !l && !r;
    }

    // delete child
    info& operator--() {
        if (l) delete l;
        if (r) delete r;
        l = r = nullptr;

        return *this;
    }

    // update info
    info& operator++() {
        int now = 0;
        if (l != nullptr) now += l->cnt;
        if (r != nullptr) now += r->cnt;
        cnt = now;
        return *this;
    }

    void setval(int val) {
        cnt += val;
    }

    ~info() {
        --(*this);
    }
};

// 动态开点线段树,两点注意
// 对一个区间 setval 的时候,它的所有值都相同,这个时候删除子节点,调用 p--
// 自顶向下递归的时候,如果没有遇到目标区间 [l, r],那么要 push 开点
// push 和普通线段树比,动态开点的 push 一般是要新建节点的

// 另外如果区间所有值都相等,那么这个区间用 leaf 标记
struct SegTree {
    info* root;

    SegTree() {
        root = new info();
    }
    ~SegTree() {
        if (root != nullptr) {
            --(*root);
            delete root;
        }
    }

    void pull(info &p) {
        ++p;
    }

    // 节点 p 对应区间是 [l, r],将 a[pos] -> val

    void change(info &p, int l, int r, int x, int val) {
        if (l >= r) {
            p.setval(val);
            return;
        }

        int mid = (l + r) >> 1;
        if (x <= mid) {
            if (!p.l) p.l = new info();
            change(*(p.l), l, mid, x, val);
        }
        else {
            if (!p.r) p.r = new info();
            change(*(p.r), mid+1, r, x, val);
        }

        pull(p);
    }

    int query(info &p, int l, int r, int x) {
        if (l >= r) return l;
        int mid = (l + r) >> 1;

        int tot = mid - l + 1;
        if (p.l) tot -= p.l->cnt;

        // 递归下去的时候动态开点
        if (x <= tot) {
            if (!p.l) p.l = new info();
            return query(*p.l, l, mid, x);
        }
        else {
            if (!p.r) p.r = new info();
            return query(*p.r, mid+1, r, x-tot);
        }
    }
};

// usage: SegTree<4 * maxn> tr(a, n)

int n, m, q, lim;
const int maxn = 3e5 + 5;
vector<vector<ll> > extra(maxn);

vector<SegTree> tr(maxn);

ll solve0(int x, bool del) {
    // tr[n+1] xth element
    // idx = 0 only operate col m
    // idx = other ? (x, y) insert to (n, m)

    int p = tr[n+1].query(*tr[n+1].root, 1, lim, x);
    tr[n+1].change(*tr[n+1].root, 1, lim, p, 1);

    ll ans = 0;
    if (p <= n) ans = 1LL * p * m;
    else ans = extra[n+1][p-n-1];

    if (del) extra[n+1].push_back(ans);

    return ans;
}

ll solve1(int x, int y) {
    int p = tr[x].query(*tr[x].root, 1, lim, y);
    tr[x].change(*tr[x].root, 1, lim, p, 1);

    ll ans = 0;
    if (p < m) ans = 1LL * (x-1) * m + p;
    else ans = extra[x][p-m];
    extra[n+1].push_back(ans);

    ll now = solve0(x, 0);
    extra[x].push_back(now);

    return ans;
}

// usage: SegTree<4 * maxn> tr(a, n)

int main() {
    //freopen("input.txt", "r", stdin);

    cin >> n >> m >> q;
    lim = max(n, m) + q;

    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);

        ll ans = 0;
        if (y == m) ans = solve0(x, 1);
        else ans = solve1(x, y);

        printf("%lld\n", ans);
    }
}