欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces:896C-Willem, Chtholly and Seniorious(odt模板)

程序员文章站 2024-02-24 10:37:52
...

题目链接:http://codeforces.com/contest/896/problem/C

C. Willem, Chtholly and Seniorious

time limit per test 2 seconds
memory limit per test 256 megabytes

Problem Description

— Willem…

— What’s the matter?

— It seems that there’s something wrong with Seniorious…

— I’ll have a look…

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.

Seniorious has n pieces of talisman. Willem puts them in a line, the i-th of which is an integer ai.

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 ≤ i ≤ r, assign ai + x to ai.
2 l r x: For each i such that l ≤ i ≤ r, assign x to ai.
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 ai such that l ≤ i ≤ r are taken and sorted into an array of non-decreasing integers. It's guaranteed that 1 ≤ x ≤ r - l + 1.
4 l r x y: Print the sum of the x-th power of ai such that l ≤ i ≤ r, modulo y, i.e. .

Input

The only line contains four integers n, m, seed, vmax (1 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 109).

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.

Examples

Input
10 10 7 9

Output
2
1
0
3

Input
10 10 9 9

Output
1
1
3
3

Note

In the first example, the initial array is {8, 9, 7, 2, 3, 1, 5, 6, 4, 8}.

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,发现这个东西有点鸡肋,还要看运气,只有在面对随机数据的时候才能降低复杂度。odt主要用于解决区间的覆盖问题,将某一段区间全改为某一值,这是在使用线段树无法维护值的时候可以用odt。
  • 参考大佬的博客:https://www.cnblogs.com/yzhang-rp-inf/p/9443659.html
#include <bits/stdc++.h>
#define sit set<node>::iterator
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;

ll n, m, seed, vmax;

struct node {
    ll l, r;
    mutable ll va;

    node(ll L, ll R=-1, ll Va=0): l(L), r(R), va(Va){}

    bool operator <(const node& o) const {//规定在set中的排序键值
        return l < o.l;
    }
};

set <node> se;

ll rd()
{
    ll ret = seed;
    seed = (seed * 7 + 13) % MOD;
    return ret;
}

sit split(ll pos) {//odt的精华
    sit it = se.lower_bound(node(pos));
    if(it!=se.end() && it->l == pos) {
        return it;
    }

    --it;

    ll l = it->l, r = it->r, va = it->va;
    se.erase(it);
    se.insert(node(l, pos-1, va));
    return se.insert(node(pos, r, va)).first;
}

ll pown(ll va, ll cnt, ll mod) {//快速幂
    ll ans = 1;
    va %= mod;
    while(cnt) {
        if(cnt&1) ans *= va;
        va *= va;
        ans %= mod;
        va %= mod;
        cnt >>= 1;
    }
    return ans;
}

ll sum(ll l, ll r, ll x, ll y) {
    sit itl = split(l), itr = split(r+1);
    ll res = 0;
    for(;itl!=itr;itl++) {
        res = (res + ((ll)(itl->r - itl->l + 1ll) % y * pown(itl->va, x, y))% y) % y;//注意长度
    }
    return res;
}

void add(ll l, ll r, ll va) {
    sit itl = split(l), itr = split(r+1);
    for(;itl!=itr;itl++) {
        itl->va += va;
    }
}

void color(ll l, ll r, ll va) {
    sit itl = split(l), itr = split(r+1);
    se.erase(itl, itr);//这里本地会发生段错误,其实真的不明白为什么交题可以过。明明itl指向的地方可能被删除
    se.insert(node(l, r, va));
}

ll kth(ll l, ll r, ll k) {
    sit itl = split(l), itr = split(r+1);
    vector <pair<ll, ll> > ve;
    for(;itl!=itr;itl++) {
        ve.push_back(pair<ll, ll>(itl->va, itl->r - itl->l + 1));
    }
    sort(ve.begin(), ve.end());//排序暴力找
    for(int i=0;i<ve.size();i++) {
        k -= ve[i].second;
        if(k <= 0)
            return ve[i].first;
    }
}

int main() {
    //freopen("1.in", "r", stdin);
    scanf("%lld%lld%lld%lld", &n, &m, &seed, &vmax);

    for(int i=1;i<=n;i++) {
        ll temp = (rd() % vmax) + 1;
        se.insert(node(i, i, temp));
    }

    se.insert(node(n+1, n+1, 0));//防止越界
    for(int i=1;i<=m;i++) {
        int op = int(rd() % 4) + 1;
        int l = int(rd() % n) + 1;
        int r = int(rd() % n) + 1;

        if (l > r)
            swap(l,r);
        int x, y;
        if (op == 3)
            x = int(rd() % (r-l+1)) + 1;
        else
            x = int(rd() % vmax) +1;
        if (op == 4)
            y = int(rd() % vmax) + 1;
        if (op == 1)
            add(l, r, ll(x));
        else if (op == 2)
            color(l, r, ll(x));
        else if (op == 3)
            cout<<kth(l,r,x)<<endl;
        else
            cout<<sum(l,r,x,y)<<endl;
    }
}