Willem, Chtholly and Seniorious
珂朵莉树
慕名而来
操作 \(3\) 直接排序是我没想到的,因为随机数据所以才能过吧
\(split\) 操作中忘了开 \(longlong\),\(wa3\)
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define It set<ran>::iterator
ll qpow(ll x, ll n, ll mod)
{
ll ans = 1;
x %= mod;
while(n)
{
if(n & 1) ans = ans * x % mod;
n >>= 1;
x = x * x % mod;
}
return ans % mod;
}
struct ran
{
int l, r;
mutable ll v;
ran(){}
ran(int _l, int _r, ll _v)
{
l = _l;
r = _r;
v = _v;
}
bool operator < (const ran &x) const
{
return l < x.l;
}
};
set<ran>st;
It split(int pos)
{
It now = st.lower_bound(ran(pos, -1, 0));
if(now != st.end() && now->l == pos) return now;
now--;
ll l = now->l, r = now->r, v = now->v;
st.erase(now);
st.insert(ran(l, pos - 1, v));
return st.insert(ran(pos, r, v)).first;
}
void add(int l, int r, ll v)
{
It itr = split(r + 1);
It itl = split(l);
for(It it=itl; it!=itr; it++)
it->v += v;
}
void merge_update(int l, int r, ll v)
{
It itr = split(r + 1), itl = split(l);
st.erase(itl, itr);
st.insert(ran(l, r, v));
}
ll query_4(int l, int r, ll x, ll y)
{
ll ans = 0;
It itr = split(r + 1), itl = split(l);
for(; itl!=itr; itl++)
ans = (ans + qpow(itl->v, x, y) * (itl->r - itl->l + 1)) % y;
return ans;
}
ll query_kth(int l, int r, ll x)
{
It itr = split(r + 1), itl = split(l);
vector<pll>temp;
while(itl != itr)
{
temp.push_back(make_pair(itl->v, itl->r - itl->l + 1));
itl++;
}
sort(temp.begin(), temp.end());
ll ans = 0;
for(int i=0; i<temp.size() && x>0; i++)
{
ans = temp[i].first;
x -= temp[i].second;
}
return ans;
}
ll seed = 0, vmax = 0;
ll rnd()
{
ll ret = seed;
seed = (seed * 7 + 13) % 1000000007;
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m >> seed >> vmax;
vector<ll>a(n + 2, -1);
// for(int i=1; i<=n; i++) a[i] = 1e9;
for(int i=1; i<=n; i++) a[i] = rnd() % vmax + 1;
// for(int i=1; i<=n; i++) cout << a[i] << " ";
// cout << "\n";
for(int i=1; i<=n; i++)
{
if(a[i] == a[i - 1]) continue;
int j = i;
while(a[j] == a[i]) j++;
st.insert(ran(i, j - 1, a[i]));
}
ll op = 0, l = 0, r = 0;
while(m--)
{
op = rnd() % 4 + 1;
l = rnd() % n + 1;
r = rnd() % n + 1;
if(l > r) swap(l, r);
ll x = 0, y = 0;
if(op == 3) x = rnd() % (r - l + 1) + 1;
else x = rnd() % vmax + 1;
if(op == 4) y = rnd() % vmax + 1;
// cout << op << " " << l << " " << r << " " << x << " " << y << "\n";
if(op == 1) add(l, r, x);
else if(op == 2) merge_update(l, r, x);
else if(op == 3) cout << query_kth(l, r, x) << "\n";
else cout << query_4(l, r, x, y) << "\n";
}
// cout << endl;
return 0;
}
标签:Willem,Chtholly,449,int,ll,itl,split,ans,now
From: https://www.cnblogs.com/dgsvygd/p/16917946.html