ODT(主要特征就是推平一段区间)
其实就是用set来维护三元组,因为数据随机所以可以证明复杂度不超过O(NlogN),其他的都是暴力维护
主要操作是split,把区间分成两个,用lowerbound,
有两点需要注意1.set里的东西不能改,所以变成了mutable(可改的const),2.s.insert返回pair类型,first是插入点的迭代器
= =sort里的比较函数ll没开wa了好久
精简版:
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
//inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const double eps=1e-8;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=200000+10,maxn=50000+10,inf=0x3f3f3f3f;
struct ODT{
struct node{
int l,r;mutable ll val;
node(int _l,int _r = -1,ll _val = 0):l(_l),r(_r),val(_val){}
bool operator <(const node&rhs)const{
return l<rhs.l;
}
};
set<node>s;
typedef set<node>::iterator sit;
void ins(int l,int r,ll val){s.insert(node(l,r,val));}
sit split(int pos)
{
sit p=s.lower_bound(node(pos));
if(p != s.end() && pos == p->l)return p;
p--;node te=*p;
s.erase(p);
s.insert(node(te.l,pos-1,te.val));
return s.insert(node(pos,te.r,te.val)).fi;
}
void add(int l,int r,ll v)
{
sit x=split(l),y=split(r+1);
for(;x!=y;x++)x->val += v;
}
void color(int l,int r,ll val)
{
sit x= split(l),y=split(r+1);
s.erase(x,y);
s.insert(node(l,r,val));
}
void kth(int l,int r,ll k)
{
sit x = split(l),y = split(r+1);
vector<pli>v;
for(;x!=y;x++)
v.pb(mp(x->val,x->r - x->l + 1));
sort(v.begin(),v.end(),[](pli a,pli b){return a.fi>b.fi;});
for(int i=(int)v.size()-1;i>=0;i--)
{
if(k<=v[i].se)
{
printf("%lld
",v[i].fi);
return ;
}
k-=v[i].se;
}
}
void sum(int l,int r,ll a,ll b)
{
sit x = split(l),y=split(r+1);
ll ans=0;
for(;x!=y;x++)
{
ans+=1ll*qp(x->val % b,a,1ll*b)*(x->r - x->l + 1)%b;
if(ans>=b)ans-=b;
}
printf("%lld
",ans);
}
void debug()
{
for(auto x:s)
printf("%d %d %d
",x.l,x.r,x.val);
puts("");
}
}o;
ll n,m,seed,vmax,a[N];
ll rnd()
{
ll ret = seed;
seed = (seed * 7ll + 13)%1000000007;
return ret;
}
int main()
{
// o.ins(1,1,3);o.ins(2,2,4),o.ins(3,5,6);
// o.add(2,3,2);
// o.debug();
scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
for(int i=1;i<=n;i++)
{
a[i] = (rnd()%vmax) + 1;
o.ins(i,i,a[i]);
}
o.ins(n+1,n+1,0);
int res=0;
for(int i=1;i<=m;i++)
{
int op = (rnd()%4) + 1;
int l = (rnd()%n) + 1;
int r = (rnd()%n) + 1;
ll x,y;
if (l > r)swap(l, r);
if (op == 3)x = (rnd()%(r - l + 1)) + 1;
else x = (rnd()%vmax) + 1;
if (op == 4)y = (rnd()%vmax) + 1;
if(op==1)o.add(l,r,x);
else if(op==2)o.color(l,r,x);
else if(op==3)o.kth(l,r,x);
else o.sum(l,r,x,y);
// o.debug();
// printf("%d %d %d %d %d
",op,l,r,x,y);
}
return 0;
}
/********************
********************/
自已刚开始意淫的一个写法:
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const double eps=1e-8;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=200000+10,maxn=50000+10,inf=0x3f3f3f3f;
struct ODT{
struct node{
int l,r;mutable ll val;
bool operator <(const node&rhs)const{
return l<rhs.l || l==rhs.l&&r<rhs.r;
}
};
set<node>s;
void split(int pos)
{
if(pos<=0)return ;
auto p=s.upper_bound(node{pos,inf,INF});
if(p==s.begin())return ;
p--;
// printf("--------%d %d %d
",p->l,p->r,p->val);
if(pos < p->l || pos >= p->r)return ;
node te=*p;
s.erase(te);
s.insert({te.l,pos,te.val});
s.insert({pos+1,te.r,te.val});
}
void add(int l,int r,ll v)
{
split(l-1),split(r);
auto x=s.lower_bound(node{l,-inf,-INF});
auto y=s.lower_bound(node{r,inf,INF});
for(;x!=y;x++)x->val += v;
}
void color(int l,int r,ll val)
{
split(l-1);split(r);
auto x=s.lower_bound(node{l,-inf,-INF});
auto y=s.lower_bound(node{r,inf,INF});
// printf("%d %d %d %d
",x->l,x->r,y->l,y->r);
s.erase(x,y);
s.insert({l,r,val});
}
void kth(int l,int r,ll k)
{
split(l-1);split(r);
auto x=s.lower_bound(node{l,-inf,-INF});
auto y=s.lower_bound(node{r,inf,INF});
vector<pli>v;
for(;x!=y;x++)
v.pb(mp(x->val,x->r - x->l + 1));
sort(v.begin(),v.end(),[](pli a,pli b){return a.fi>b.fi;});
for(int i=(int)v.size()-1;i>=0;i--)
{
if(k<=v[i].se)
{
printf("%lld
",v[i].fi);
return ;
}
k-=v[i].se;
}
}
void sum(int l,int r,ll a,ll b)
{
split(l-1);split(r);
auto x=s.lower_bound(node{l,-inf,-INF});
auto y=s.lower_bound(node{r,inf,INF});
ll ans=0;
for(;x!=y;x++)
{
ans+=1ll*qp(x->val % b,a,1ll*b)*(x->r - x->l + 1)%b;
if(ans>=b)ans-=b;
}
printf("%lld
",ans);
}
void debug()
{
for(auto x:s)
printf("%d %d %d
",x.l,x.r,x.val);
puts("");
}
}o;
ll n,m,seed,vmax,a[N];
ll rnd()
{
ll ret = seed;
seed = (seed * 7ll + 13)%1000000007;
return ret;
}
int main()
{
scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
for(int i=1;i<=n;i++)
{
a[i] = (rnd()%vmax) + 1;
o.s.insert({i,i,a[i]});
}
// o.debug();
for(int i=1;i<=m;i++)
{
int op = (rnd()%4) + 1;
int l = (rnd()%n) + 1;
int r = (rnd()%n) + 1;
ll x,y;
if (l > r)swap(l, r);
if (op == 3)x = (rnd()%(r - l + 1)) + 1;
else x = (rnd()%vmax) + 1;
if (op == 4)y = (rnd()%vmax) + 1;
if(op==1)o.add(l,r,x);
else if(op==2)o.color(l,r,x);
else if(op==3)o.kth(l,r,x);
else o.sum(l,r,x,y);
// o.debug();
// printf("%d %d %d %d %d
",op,l,r,x,y);
}
return 0;
}
/********************
********************/