# ucup 3-36

## PC
J

## chat

TKO:後ろから
yuma:前
kuma:F~

## A AC
クエリ static
長さnの二つの数列aとwが与えられる
クエリ[l,r]に対して以下を答える
1<=p_1<...<p_k<=n, 1<=a_p_1<=...<=a_p_k<=n を満たすp_1,...,p_kであってこれらがいずれも[l,r]に含まれないようなものに対して、sum w_p_iの最大化

左右前計算した数列をそれぞれL,Rとする
i<lかつr<jであってa_i<=a_jを満たすものに対してL_i+R_jの最大化をしたい
RollbackMo + 永続セグ木でとりあえず解ける　O(N)個の永続化は流石にまずい

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())

using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template <typename T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T, typename U> T ceil(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U> T floor(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T> int popcnt(T x) {
    return __builtin_popcountll(x);
}
template <typename T> int topbit(T x) {
    return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T> int lowbit(T x) {
    return (x == 0 ? -1 : __builtin_ctzll(x));
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "P(" << p.first << ", " << p.second << ")";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
    os << "{";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if (itr != map_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T> void _show(int i, T name) {
    cerr << '\n';
}
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
    for (; a[i] != ',' && a[i] != '\0'; i++)
        cerr << a[i];
    cerr << ":" << b << " ";
    _show(i + 1, a, c...);
}

/**
* @brief template
*/

struct RollbackMo{
    using P=array<int,2>;
    int n;
    vector<P> qs;
    RollbackMo(int _n):n(_n){}
    void add(int lb,int rb){qs.push_back({lb,rb});}
    template<typename INIT,typename ADD,typename SNAP,typename ROLL,typename OUT>
    void run(const INIT& init,const ADD& insert,const SNAP& snapshot,const ROLL& rollback,const OUT& out){
        const int q=qs.size();
        const int w=max(1,int(n/sqrt(q+1)));
        vector<int> ord(q);
        iota(ALL(ord),0);
        sort(ALL(ord),[&](int i,int j){
            return P{qs[i][0]/w,qs[i][1]}<P{qs[j][0]/w,qs[j][1]};
        });
        init();
        snapshot();
        int last=-1,r=0;
        for(auto& i:ord)if(qs[i][1]-qs[i][0]<w){
            rep(j,qs[i][0],qs[i][1])insert(j);
            out(i);
            rollback();
        }
        for(auto& i:ord)if(qs[i][1]-qs[i][0]>=w){
            int b=qs[i][0]/w;
            if(last!=b){
                init();
                last=b;
                r=(b+1)*w;
            }
            while(r<qs[i][1])insert(r++);
            snapshot();
            for(int j=(b+1)*w-1;j>=qs[i][0];j--)insert(j);
            out(i);
            rollback();
        }
    }
};

/**
 * @brief Rollback Mo
 * @docs docs/rollbackmo.md
 */

 template <typename M, typename N, M (*f)(M, M), M (*g)(M, N), M (*m1)()>
struct PersistentSegmentTree {
    struct Node {
        M val;
        Node *l, *r;
    };
    using NP = Node *;
private:
    int n;
    NP merge(NP l, NP r) const {return new Node{f(l->val, r->val), l, r};}
    NP run(int l, int r, vector<M> &v) const {
        if (l+1 == r) return new Node{v[l], nullptr, nullptr};
        NP lp = run(l, (l+r)/2, v);
        NP rp = run((l+r)/2, r, v);
        return merge(lp,rp);
    }
    NP set(int k, const M &x, NP p, int l, int r) const {
        if (r <= k || k < l) return p;
        if (k <= l && r <= k+1) return new Node{x,nullptr,nullptr};
        return merge(set(k,x,p->l,l,(l+r)/2), set(k,x,p->r,(l+r)/2,r));
    }
    NP update(int k, const N &x, NP p, int l, int r) const {
        if (r <= k || k < l) return p;
        if (k <= l && r <= k+1) return new Node{g(p->val,x),nullptr,nullptr};
        return merge(update(k,x,p->l,l,(l+r)/2), update(k,x,p->r,(l+r)/2,r));
    }
    M query(int a, int b, NP p, int l, int r) const {
        if (r <= a || b <= l) return m1();
        if (a <= l && r <= b) return p->val;
        return f(query(a,b,p->l,l,(l+r)/2), query(a,b,p->r,(l+r)/2,r));
    }
public:
    NP root;
    PersistentSegmentTree(int _n = 0) : n(_n), root(nullptr) {}
    void run(vector<M> &v) {
        root = run(0,n,v);
    }
    void set(int k, const M &x) {
        root = set(k,x,root,0,n);
    }
    void update(int k, const N &x) {
        root = update(k,x,root,0,n);
    }
    M query(int a, int b) const {
        return query(a,b,root,0,n);
    }
};

/**
 * @brief Persistent Segment Tree
 */

 template <typename M, typename N, M (*f)(M, M), M (*g)(M, N), M (*m1)()>
struct SegmentTree {
    int sz, n;
    vector<M> data;
    SegmentTree(int _n = 0) : n(_n) {
        sz = 1;
        while (sz < _n)
            sz <<= 1;
        data.assign(2 * sz, m1());
    }
    void run(vector<M> &v) {
        for (int i = 0; i < (int)v.size(); i++)
            data[i + sz] = v[i];
        for (int k = sz - 1; k > 0; k--)
            data[k] = f(data[2 * k], data[2 * k + 1]);
    }
    void set(int k, const M &x) {
        k += sz;
        data[k] = x;
        while (k >>= 1)
            data[k] = f(data[2 * k], data[2 * k + 1]);
    }
    void update(int k, const N &x) {
        k += sz;
        data[k] = g(data[k], x);
        while (k >>= 1)
            data[k] = f(data[2 * k], data[2 * k + 1]);
    }
    M query(int a, int b) {
        M L = m1(), R = m1();
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1)
                L = f(L, data[a++]);
            if (b & 1)
                R = f(data[--b], R);
        }
        return f(L, R);
    }
    M operator[](const int &k) const {
        return data[k + sz];
    }
    vector<M> get() {
        return {data.begin() + sz, data.begin() + sz + n};
    }
    template <class F> int max_right(int L, F ch) const {
        int l = sz + L, w = 1;
        M ansL = m1();
        for (; L + w <= sz; l >>= 1, w <<= 1)
            if (l & 1) {
                if (not ch(f(ansL, data[l])))
                    break;
                ansL = f(ansL, data[l++]);
                L += w;
            }
        while (l <<= 1, w >>= 1) {
            if (L + w <= sz && ch(f(ansL, data[l]))) {
                ansL = f(ansL, data[l++]);
                L += w;
            }
        }
        return L;
    }
    template <class F> int min_left(int R, F ch) const {
        int r = sz + R, w = 1;
        M ansR = m1();
        for (; R - w >= 0; r >>= 1, w <<= 1)
            if (r & 1) {
                if (not ch(f(data[r - 1], ansR)))
                    break;
                ansR = f(data[--r], ansR);
                R -= w;
            }
        while (r <<= 1, w >>= 1) {
            if (R - w >= 0 && ch(f(data[r - 1], ansR))) {
                ansR = f(data[--r], ansR);
                R -= w;
            }
        }
        return R;
    }
};

/**
 * @brief Segment Tree
 */

int f(int A, int B) {return max(A,B);}
int g(int A, int B) {return max(A,B);}
int e() {return 0;}

using PST = PersistentSegmentTree<int,int,f,g,e>;

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N), X(N);
    rep(i,0,N) cin >> A[i] >> X[i], A[i]--;
    vector<int> L(N), R(N);
    {
        SegmentTree<int,int,f,g,e> Seg(N);
        rep(i,0,N) {
            L[i] = X[i] + Seg.query(0,A[i]+1);
            Seg.update(A[i],L[i]);
        }
    }
    {
        SegmentTree<int,int,f,g,e> Seg(N);
        rrep(i,0,N) {
            R[i] = X[i] + Seg.query(A[i],N);
            Seg.update(A[i],R[i]);
        }
    }
    vector<PST> SegL(N+1), SegR(N+1);
    vector<int> v(N,0);
    SegL[0] = PST(N);
    SegL[0].run(v);
    rep(i,0,N) {
        SegL[i+1] = SegL[i];
        SegL[i+1].update(A[i],L[i]);
    }
    SegR[N] = PST(N);
    SegR[N].run(v);
    rrep(i,0,N) {
        SegR[i] = SegR[i+1];
        SegR[i].update(A[N-1-i],R[N-1-i]);
    }
    rep(i,0,Q) {
        int l, r;
        cin >> l >> r;
        l--;
        int itl = 0, itr = N;
        int ANS = 0;
        while(itl < l) {
            chmax(ANS, L[itl] + SegR[itr].query(A[itl], N));
            itl++;
        }
        while(r < itr) {
            itr--;
            chmax(ANS, R[itr] + SegL[itl].query(0,A[itr]+1));
        }
        cout << ANS << endl;
    }
}

## B AC
マルチテスト
a_1,...,a_mが与えられる。
各1<=i<=mに対し、「1以上n以下の整数で、a_iの倍数であって、a_1,...,a_(i-1)の倍数でないものの個数」を出力

1<=x<=nに対し、xが加算されるタイミング(=xの約数のうち数列aで一番早く登場するもの)を観ればよい

## C
クエリ
n*n行列a(n<=1000)が与えられる
以下の操作をしながら、行列の要素の最大公約数を出力
(+,t) i+j=tとなるi,jに対し、a_{i,j}を文字列としてreverse
(-,t) i-j=tとなるi,jに対し、a_{i,j}を文字列としてreverse

n<=10^3, q<=10^6

流石に reverse は非本質？ 19,91 とかいい性質あるとは思えず
n^2 個の gcd だから大体小さくなる

45 度回転
集合 S,T について以下を処理できればよい
S または T に要素を一つ追加 / 削除し，gcd \{a[i,j] | i in S, j in T\} を求める

簡単にはなっていなさそう…

主客転倒をする？
クエリを K 回おきに分割する
Q/K 回いい感じの前処理をする
K 回中に変更されるマスは，全く同じ操作をされるものはまとめて考えれば重複込みで O(K^2) 個→全体 O(QK)

あんまりいい感じにならない…　分割の方針は sqrt(Q) をもってこないとダメそう

前処理 O(N*Q/K) とかになってほしい

制約で末尾 0 じゃないから結局 行/列 で reverse + 全体 gcd

a[0][0],rev(a[0][0])の素因数(<=20個)だけ持つ
行・列flip、全体minが出来ればよい

全体min >= k の判定問題考えたら
「ある行と列が mod 2 で同じ/違う回数 flip」の形の条件になる
関係を O(N) 頂点のグラフで表せば UF でクエリ O(a(N)) ?

## D AC
0,...,nとラベリングされたマスの上をロボットが動く
一回の操作で右か左に動く　操作列をLとRの文字列で表すことにする
最初はマス0からスタートして、最後もマス0にいなくてはいけない
マスiを踏む回数が丁度c_iであるとき、可能かどうかを判定し、可能ならば辞書順最小の操作列を出力

各隣接マスの間の移動回数が具体的に計算できる
非連結にならないように動く
Rのあとはできる限りLを打ちたい　貪欲でよさそう
必要十分条件は交代和が0かつ間のマスを2回以上踏む(右端に到達して、もどらないといけない)

## E

ゲーム
- n 個の金塊が (xi,yi) にある, yi<0←非本質
- player は (p,0) にいる
- 金塊を k 個集めるのが目標
- ユークリッド距離 s にある金塊を得るにはコストが s^2 かかる
- コストを最小化したい

q 個のクエリ：ai,bi,ki が与えられる．p を [ai,bi] 上の一様な実数乱数，k=ki としたときのコストの期待値を mod 10^9+7 で求めよ．

n<=2000, q<=2×10^5

(p-xi)^2 +yi^2 小さい方から k 個の sum の期待値

p^2 は外に出せるので -2xi*p+xi^2 +yi^2

## F AC
頂点に色付きの有向グラフと整数 k が与えられる
「任意の長さ k 以下の simple path について，含まれる頂点の色はdistinct」か判定
n,m,k<=10^5, 色種類<=50

同じ色で距離 k 未満の頂点がなければよい
色ごとに bfs すればよい？
C=50 で O(C(n+m)) とか

## G AC
tariff p_1,...,p_n ははじめすべて 1
「ある i を選び，p_i に t_i/100 を加える」ことを k 回おこなう
p_i 総積の max を求めよ

T<=5000,n<=40,k<=10^6
sum k の制約はない
TL 1sec

l_i:足す回数

Sample2がでかすぎる

l_i/t_iの閾値をにぶたん？
閾値までl_iを増やして、余った回数がn+eps以上なら閾値を増やす
n+eps以下なら下のシミュをpqなどでやる
計算量O(Tnlog eps)　それっぽいが...

naive にシミュレーションするなら (100+(l+1)t)/(100+lt) を大きい方から掛ければよい

sum l_i <= k
{100020, 100018, 100017, 100015, 100013, 100009, 100004, 99996, 99979, 99929}

a_ia_jb_j*100a_iとa_ia_jb_i*100a_jの比較
-> b_i+100/a_iを一定に？

タイブレークは気にしなくてよい（次に操作されるのは等しいものなので）

## H

n×m のグリッド
d 個の砂糖：砂糖はおいしさをもつ
p 個の長方形の障害物：障害物同士は角も含めて接触しない

q 個のクエリ：あるマスに k 個のコマが置かれている．
コマは (x,y) から (x+1,y) か (x,y+1) に動ける
好きなだけ駒を動かして，取った砂糖のおいしさの sum を最大化

n×m <= 10^6, k <= 5
TL 4sec

## I AC

## J AC
n×mのチョコ
各マスはおいしさをもつ
Putata, Budada が交互に，後ろのいくつかの行 or 列を一つ選んで全部食べることを繰り返す
残りのおいしさの総和が s 以下になったら最後に食べた方が怒られる

q 個のクエリ： s が与えられるので怒られる方を出力

sの昇順に処理したい
Grundy数をinlineに更新したい感じ
ダメなマスをxとして、上or左に
xx
xo
なるoマスがあれば勝ち

tableauxが(incrementalに)与えられます
両者とも上or右に何マスでもいける
勝つのはどっち？

判定条件をきれいに書きたい
長方形のとき:H=Wが必要十分(gr=i xor j)

H!=W:先手

ooo
ooo
oo
:後手

oo
o
:先手

## K
shakyな列とは問題文参照
与えられる列からdisjointな連続部分列を出来るだけ取り出して、各区間がshakyな(連続とは限らない)部分列があるようにする

shakyは外側のsumが影響が大きい

## L AC
嘘つきと「本当とウソどちらもつくやつ」がいる。iは「aiは嘘つき」と主張している
嘘つきの人数の最大値

なもりグラフ上で、出来るだけ黒く塗りたい
黒同士がつながってはいけない

ループが偶数なら二部グラフなのでやるだけ
奇数だと円環DPでできるが面倒

## M AC
interactive
三角形分割の特定？

u=1とした時の返り値の列を考える(v=n,1,2に対しては0としておく)
0が返ってきたら分割できるので、0が返ってこない(=1とつながっている辺が存在しない)とする
この時、辺(n,2)が存在する。三角形(n,1,2)を取り除く
返ったクエリ列をすべて1減らして、「頂点2に対してクエリを行った」ことにしてよい　再帰的に決定できる