珂朵莉树
ODT 来源 CF896C
适用范围
是一种支持以下操作的暴力算法:
- 区间修改
- 区间赋值
- 求区间内的第 \(k\) 小
- 求区间 \(k\) 次方和
ODT 本质上是建立在区间赋值的一种操作，有区间赋值的操作的话可以保证时间复杂度均摊为 \(O(n \log \log n)\)，但是如果没有区间赋值，而只有单点赋值，则将会导致 ODT 被卡到 \(O(n ^ 2)\)， 同时如果是在出题人的精心设计的数据下，ODT也会被卡。但是数据如果是随机的（CCF的）就可以以近乎线性的优秀复杂度过掉。
code time(主要是不想讲原理了)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
#define fom(i, a) for(int i=a; i; -- i)
#define foa(i, a, b) for(int i=a; i < b; ++ i)
#define fos(i, a, b) for(int i=a; i <= b; ++ i)
#define fop(i, a, b) for(int i=a; i >= b; -- i)
namespace IO
{
#define fdt(ch) for(; isdigit(ch); ch=gc())
#define fsp(ch) for(; !isdigit(ch); ch=gc())
int pp1=-1; const int pp2=(1<<21)-1; char buf[1<<21],*p1=buf,*p2=buf,buffer[1<<21];
inline void flush() {fwrite(buffer,1,pp1+1,stdout); pp1=-1;}
inline void pc(const char ch) {if(pp1==pp2) flush(); buffer[++pp1]=ch; }
inline char gc(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
template <class T> inline void read(T &res){char ch=gc();bool f=0;res=0; fsp(ch) f|=ch=='-'; fdt(ch) res=(res<<1)+(res<<3)+(ch^48); res=f?~res+1:res;}
template <class T> inline void ww(T x) { if(!x) pc('0'); else { static int stk[20]; int top=0;if(x<0)x=~x+1,pc('-');while(x) stk[top++]=x%10, x/=10; while(top--) pc(stk[top]^48);} }
}
#define ws IO::pc(' ')
#define wl IO::pc('\n')
#define ww(x) IO::ww(x)
#define read(x) IO::read(x)
#define flush() IO::flush()
const ll N = 1e5 + 2, P = 1e9 + 7;
struct node
{
ll l, r;
mutable ll v;
node (ll l, ll r = 0, ll v = 0) : l(l), r(r), v(v) {};
bool operator <(const node &x) const { return l < x.l; }
};
ll n, m, seed, vmax, a[N];
set<node> s;
// #define swap(l, r) (l ^= r ^= l ^= r)
set<node>::iterator split(ll pos)
{
auto it = s.lower_bound(node(pos));
if(it != s.end() && it -> l == pos) return it;
it --;
// if(it -> r < pos) return s.end();
ll l = it -> l, r = it -> r, v = it -> v;
s.erase(it);
s.insert((node){l, pos - 1, v});
return s.insert(node(pos, r, v)).first;
}
inline void add(ll l, ll r, ll x)
{
auto itr = split(r + 1), itl = split(l);
for(auto it = itl; it != itr; ++ it) it -> v += x;
}
inline void assign(ll l, ll r, ll x)
{
auto itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, x));
}
struct Rank
{
ll num, cnt;
bool operator <(const Rank &x) const { return num < x.num; }
Rank(ll num, ll cnt) : num(num), cnt(cnt) {}
};
inline ll rnk(ll l, ll r, ll x)
{
auto itr = split(r + 1), itl = split(l);
vector<Rank> v;
for(auto it = itl; it != itr; ++ it) v.push_back(Rank(it -> v, (it -> r) - (it -> l) + 1));
sort(v.begin(), v.end());
// for(auto t : v) if(t.cnt < x) x -= t.cnt; else return t.num;
ll i;
for(i = 0; i < v.size(); ++ i) if(v[i].cnt < x) x -= v[i].cnt; else break;
return v[i].num;
}
inline ll qmi(ll a, ll k, ll p)
{
ll res = 1; a %= p;
while(k)
{
if(k & 1) res = (a * res) % p;
a = (a * a) % p, k >>= 1;
}
return res;
}
inline ll calcP(ll l, ll r, ll x, ll y)
{
auto itr = split(r + 1), itl = split(l);
ll ans = 0;
for(auto it = itl; it != itr; ++ it ) ans = (ans + qmi(it -> v, x, y) * ((it -> r) - (it -> l) + 1) % y) % y;
return ans;
}
inline ll rnd()
{
ll ret = seed;
seed = (seed * 7 + 13) % P;
return ret;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
#endif
read(n), read(m), read(seed), read(vmax);
// cin >> n >> m >> seed >> vmax;
fos(i, 1, n) a[i] = (rnd() % vmax) + 1, s.insert((node){i, i, a[i]});
s.insert((node)(n + 1, n + 1, 0));
fos(i, 1, m)
{
ll op, l, r, x, y;
op = (rnd() % 4) + 1;
l = (rnd() % n) + 1; r = (rnd() % n) + 1;
if(l > r) swap(l, r);
x = (op == 3) ? (rnd() % (r - l + 1)) + 1 : (rnd() % vmax) + 1;
if(op == 4) y = (rnd() % vmax) + 1;
// ww(op), wl;
if(op == 1) add(l, r, x);
else if(op == 2) assign(l, r, x);
else if(op == 3) ww(rnk(l, r, x)), wl;
else ww(calcP(l, r, x, y)), wl;
// else if(op == 3) cout << rnk(l, r, x) << endl;
// else cout << calcP(l, r, x, y) << endl;
// cout << op << " " << l << " " << r << " " << x << " " << y << endl;
}
flush();
return 0;
}