CF896C Willem, Chtholly and Seniorious < ODT >

Problem

Willem, Chtholly and Seniorious

$\mathrm{Time\;Limit\;per\;test:\;2\;seconds}$
$\mathrm{Memory\;Limit\;per\;test:\;256\;megabytes}$
$\mathrm{input:\;standard\;input}$
\mathrm{output:\;standard\;output

Description

— Willem…
— What’s the matter?
— It seems that there’s something wrong with Seniorious…
— I’ll have a look…


$\mathrm{Seniorious}$ is made by linking special talismans in particular order.
After over $500$ years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.
$\mathrm{Seniorious}$ has $n$ pieces of talisman. Willem puts them in a line, the $i^{th}$ of which is an integer $a_i$.
In order to maintain it, Willem needs to perform $m$ operations.
There are four types of operations:

1. $l\;r\;x$: For each $i$ such that $l\le i\le r$, assign $a_i+x$ to $a_i$.
2. $l\;r\;x$: For each $i$ such that $l\le i\le r$, assign $x$ to $a_i$.
3. $l\;r\;x$: Print the $x^{th}$ smallest number in the index range $[l,r]$, i.e. the element at the $x^{th}$ position if all the elements $a_i$ such that $l≤i≤r$ are taken and sorted into an array of non-decreasing integers. It’s guaranteed that $1\le x\le r-l+1$.
4. $l\;r\;x\;y$: Print the sum of the $x^{th}$ power of $a_i$ such that $l\le i\le r$, modulo $y$, i.e. $(\sum_{i=l}^{r}{a_i^x})\mod{y}$.

Input

The only line contains four integers $n,m,seed,vmax$ ($1\le n,m\le10^5$,$0\le seed<10^9+7$,$1\le vmax\le10^9)$.
The initial values and operations are generated using following pseudo code:

def rnd():
    ret = seed
    seed = (seed * 7 + 13) mod 1000000007
    return ret

for i = 1 to n:
    a[i] = (rnd() mod vmax) + 1

for i = 1 to m:
    op = (rnd() mod 4) + 1
    l = (rnd() mod n) + 1
    r = (rnd() mod n) + 1
    if (l > r): 
         swap(l, r)
    if (op == 3):
        x = (rnd() mod (r - l + 1)) + 1
    else:
        x = (rnd() mod vmax) + 1
    if (op == 4):
        y = (rnd() mod vmax) + 1

Here $op$ is the type of the operation mentioned in the legend.

Output

For each operation of types $3$ or $4$, output a line containing the answer.

Example

Input 1

10 10 7 9

Output 1

2
1
0
3

Input 2

10 10 9 9

Output 2

1
1
3
3

Note

In the first example, the initial array is $\lbrace8,9,7,2,3,1,5,6,4,8\rbrace$.
The operations are:
$2\;6\;7\;9$
$1\;3\;10\;8$
$4\;4\;6\;2\;4$
$1\;4\;5\;8$
$2\;1\;7\;1$
$4\;7\;9\;4\;4$
$1\;2\;7\;9$
$4\;5\;8\;1\;1$
$2\;5\;7\;5$
$4\;3\;10\;8\;5$

标签：ODT

Translation

给出一个长为$10^5$级别的初始数组，要求维护四种操作：

1. 将$a_l \sim a_r$中的每个数$+x$
2. 将$a_l\sim a_r$中的每个数赋为$x$
3. 询问区间$[l,r]$中的第$x$小值
4. 询问$(\sum_{i=l}^{r}{a_i^x})\mod{y}$

Solution

$\mathrm{ODT}$裸题。

用一棵set维护若干区间，每个区间都是值相等的一段。
对于操作$1$，将与$[l,r]$有交集的所有区间都拿出来，如果是包含的区间，可以直接将区间值$+x$；如果是部分相交，则把区间拆成两部分（或三部分），分别赋值后删除原区间，插入新区间。
对于操作$2$，将所有包含区间提出并删除，分成至多三段，即$[pre,l),[l,r],(r,suc]$，其中$pre$和$suc$是与$[l,r]$部分相交的两个区间的左端点和右端点。将左右两个区间赋值为原来的值，将中间的区间赋值为$x$。
对于询问$3$，将所有相交区间合起来排序再枚举判断即可。
对于询问$4$，将所有相交区间提出来得到每个值的个数，直接统计贡献即可。

复杂度证明见lxl的题解

Code

#include <bits/stdc++.h>
#define fir first
#define sec second
#define MAX_N 100000
#define MOD 1000000007
using namespace std;
typedef long long lnt;
typedef pair<int,int> pii;
typedef pair<lnt,int> pli;
typedef map<pii,lnt>::iterator IT;
map <pii, lnt> s;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, seed, vmx, a[MAX_N+5];
int rnd() {int ret = seed; return seed = (int)((7LL*seed+13)%MOD), ret;}
void qry(int &op, int &l, int &r, int &x, int &y) {
    op = rnd()%4+1, l = rnd()%n+1, r = rnd()%n+1; if (l > r) swap(l, r);
    x = rnd()%(op == 3 ? (r-l+1) : vmx)+1; y = op == 4 ? rnd()%vmx+1 : 0;
}
lnt pw(lnt x, lnt k, lnt p) {
    lnt ret = 1LL; x %= p;
    for (; k; k>>=1, (x *= x) %= p)
        if (k&1) (ret *= x) %= p;
    return ret;
}
int main() {
    read(n), read(m), read(seed), read(vmx);
    for (int i = 1; i <= n; i++) a[i] = rnd()%vmx+1;
    for (int i = 1; i <= n; i++) s[pii(i, i)] = a[i];
    for (int i = 1, op, l, r, x, y; i <= m; i++) {
        qry(op, l, r, x, y); IT it = s.lower_bound(pii(l, l));
        if (op == 1) {
            if (it->fir.fir != l) {
                it--;
                pii pr = pii(it->fir.fir, l-1), cur = pii(l, min(r, it->fir.sec));
                if (it->fir.sec <= r) s[pr] = it->sec, s[cur] = it->sec+x;
                else s[pr] = it->sec, s[cur] = it->sec+x, s[pii(r+1, it->fir.sec)] = it->sec;
                s.erase(it), it = s.lower_bound(pii(l+1, l+1));
            }
            for (; it != s.end() && it->fir.fir <= r; it++)
                if (it->fir.sec <= r) it->sec += x;
                else {
                    s[pii(it->fir.fir, r)] = it->sec+x, 
                    s[pii(r+1, it->fir.sec)] = it->sec, 
                    s.erase(it); break;
                }
        }
        if (op == 2) {
            if (it->fir.fir != l) {
                it--; pii pr = pii(it->fir.fir, l-1);
                if (it->fir.sec > r) s[pii(r+1, it->fir.sec)] = it->sec;
                s[pr] = it->sec, s.erase(it), it = s.lower_bound(pii(l+1, l+1));
            }
            for (; it != s.end() && it->fir.fir <= r; s.erase(it), it = s.lower_bound(pii(l, l)))
                if (it->fir.sec > r) s[pii(r+1, it->fir.sec)] = it->sec;
            s[pii(l, r)] = x;
        }
        if (op == 3) {
            vector <pli> vec;
            if (it->fir.fir != l)
                it--, vec.push_back(pli(it->sec, min(r, it->fir.sec)-l+1)), it++;
            for (; it != s.end() && it->fir.fir <= r; it++)
                vec.push_back(pli(it->sec, min(r, it->fir.sec)-it->fir.fir+1));
            sort(vec.begin(), vec.end());
            for (int j = 0; j < (int)vec.size(); x -= vec[j++].sec)
                if (x <= vec[j].sec) {printf("%lld\n", vec[j].fir); break;}
        }
        if (op == 4) {
            lnt ans = 0;
            if (it->fir.fir != l)
                it--, (ans += pw(it->sec, x, y)*(min(r, it->fir.sec)-l+1)%y) %= y, it++;
            for (; it != s.end() && it->fir.fir <= r; it++)
                (ans += pw(it->sec, x, y)*(min(r, it->fir.sec)-it->fir.fir+1)%y) %= y;
            printf("%lld\n", ans);
        }
    }
    return 0;
}