题意
题目链接
sol
odt板子题。就是用set维护连续段的大暴力。。
然鹅我抄的板子本题re提交ac??。。
具体来说,用50 50 658073485 946088556
这个数据测试下面的代码,然后在79行停住,看一下bg和i的值会发生神奇的事情。。
问题已解决,确实是那位博主写错了, 只要把split(l)和split(r + 1)反过来就行了
#include<bits/stdc++.h> #define ll long long #define int long long #define sit set<node>::iterator #define fi first #define se second using namespace std; const int mod = 1e9 + 7, maxn = 1e6 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, mod; template<typename a, typename b> inline int mul(a x, b y) { return 1ll * x * y % mod; } template<typename a, typename b> inline void add2(a &x, b y) { x = (x + y % mod); } ll seed, vmax; int a[maxn]; int rnd() { int ret = seed; seed = (seed * 7 + 13) % mod; return ret; } struct node { int l, r; mutable ll v; bool operator < (const node &rhs) const { return l < rhs.l; } }; set<node> s; sit split(int p) { auto pos = s.lower_bound({p}); if(pos != s.end() && pos->l == p) return pos; pos--; int l = pos->l, r = pos->r, v = pos->v; s.erase(pos); s.insert({l, p - 1, v}); return s.insert({p, r, v}).fi; } void add(int l, int r, int val) { auto bg = split(l), ed = split(r + 1); for(auto i = bg; i != ed; i++) i->v += val; } void mem(int l, int r, int val) { for(int i = l; i <= r; i++) a[i] = val; auto bg = split(l), ed = split(r + 1); s.erase(bg, ed); s.insert({l, r, val}); } int rak(int l, int r, int x) { vector<pair<ll, int>> v; auto bg = split(l), ed = split(r + 1); for(auto i = bg; i != ed; i++) v.push_back({i->v, i->r - i->l + 1}); sort(v.begin(), v.end()); for(auto it = v.begin(); it != v.end(); it++) { x -= it -> se; if(x <= 0) return it -> fi; } assert(0); } int fp(int a, int p) { int base = 1; a %= mod; while(p) { if(p & 1) base = 1ll * base * a % mod; a = 1ll * a * a % mod; p >>= 1; } return base; } int po(int l, int r, int x) { if(l == 6 && r == 7) { puts("g"); } auto bg = split(l); printf("%d %d %d %dn", bg->l, bg->r, bg->v); auto ed = split(r + 1); int ans = 0; for(sit i = bg; i != ed; i++) { printf("%d %d %d %dn", i->l, i->r, i->v); ans = (ans + (i->r - i->l + 1) * fp(i->v, x) % mod) % mod; } return ans; } signed main() { n = read(); m = read(); seed = read(); vmax = read(); for(int i = 1; i <= n; i++) a[i] = (rnd() % vmax) + 1, s.insert({i, i, a[i]}); s.insert({n + 1, n + 1, 0}); for(int i = 1; i <= m; i++) { int op = (rnd() % 4) + 1; int l = (rnd() % n) + 1; int r = (rnd() % n) + 1, x = -1; if(l > r) swap(l, r); if(op == 3) x = (rnd() % (r - l + 1)) + 1; else x = (rnd() % vmax) + 1; if(op == 4) mod = (rnd() % vmax) + 1; if(op == 1) add(l, r, x); else if(op == 2) mem(l, r, x); else if(op == 3) cout << rak(l, r, x) << 'n'; else cout << po(l, r, x) << 'n'; } return 0; } /* 50 50 658073485 946088556 */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605281.html