大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
操作关键:推平一段区间
cf 896c
题意:操作分四种,
区间加上一个数、区间赋值、求区间第k小、求区间幂次和
- 将序列中连续的相同的元素整合、用一个三元组(L,R,val)来表示
- set维护
- 定义内部类:
struct node
{
int l,r; //区间的左端点、右端点
mutable LL v; //数值
node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {
} //初始化
bool operator<(const node& o) const //重载运算符
{
return l < o.l;//从小到大
}
};
4.珂朵莉树的核心操作:split
#define IT set<node>::iterator //position在【l,r】的范围里,把它分成【l,pos-1】和【pos,r】两个区间
IT split(int pos)
{
IT it = s.lower_bound(node(pos)); //找到首个不小于pos的set
if (it != s.end() && it->l == pos) //无需,直接返回
return it;
--it; //否则一定在前一个区间中
int L = it->l, R = it->r; //【l,r】就是要分裂的区间
LL V = it->v; //取出值
s.erase(it); //删除原集合
s.insert(node(L, pos-1, V)); //构建前半段的新结合
return s.insert(node(pos, R, V)).first; //构建后半段的新集合并且返回地址
}
5.维护加减
void add(int l, int r, LL val)
{
IT itr = split(r+1),itl = split(l); //左闭右开的区间
for (; itl != itr; ++itl)
itl->v += val;
}//对所有三元组进行维护
6.推平操作
//区间赋值
void assign_val(int l, int r, LL val)
{
IT itr = split(r+1),itl = split(l); //求出要被摊平区间的收尾地址
s.erase(itl, itr); //删除原集合
s.insert(node(l, r, val)); //添加新集合
}
7.求第k小
将这一段取出,排序,找到第k大的数
LL rank(int l, int r, int k)
{
vector<pair<LL, int> > vp;
IT itr = split(r+1),itl = split(l);
vp.clear();
for (; itl != itr; ++itl)
vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + 1));
sort(vp.begin(), vp.end());
for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it)
{
k -= it->second;
if (k <= 0)
return it->first;
}
}
8.区间幂次和
LL pown(LL a, LL b, LL mod)
{
LL res = 1;
LL ans = a % mod;
while (b)
{
if (b&1)
res = res * ans % mod;
ans = ans * ans % mod;
b>>=1;
}
return res;
}
LL sum(int l, int r, int ex, int mod)
{
IT itr = split(r+1),itl = split(l);
LL res = 0;
for (; itl != itr; ++itl)
res = (res + (LL)(itl->r - itl->l + 1) * pown(itl->v, LL(ex), LL(mod))) % mod;//快速幂
return res;
}
完整代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
#define IT set<node>::iterator
const int MAXN=1e5+7;
const int MOD7=1e9+7;
struct node{
int l,r;
mutable LL v;
node(int L,int R=-1,LL V=0):l(L),r(R),v(V){
}
bool operator<(const node &o)const{
return l<o.l;
}
};
LL qpow(LL a,LL b,LL mod){
//快速幂
LL ans=1;
LL x=a%mod;
while(b){
if(b&1)ans=ans*x%mod;
x=x*x%mod;
b>>=1;
}
return ans;
}
set<node>s;
IT split(int pos){
IT it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos)return it;
--it;
int L=it->l,R=it->r;
LL V=it->v;
s.erase(it);
s.insert(node(L,pos-1,V));
return s.insert(node(pos,R,V)).first;
}
void add(int l,int r,LL val){
//给l到r所有数加上val
IT itr=split(r+1),itl=split(l);
for(;itl!=itr;++itl)
itl->v+=val;
}
void assign_val(int l,int r,LL val){
//把l到r所有数改为val
IT itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(node(l,r,val));
}
LL ranks(int l,int r,int k){
//询问l到r区间第k小
vector<pair<LL,int> >vp;
IT itr=split(r+1),itl=split(l);
vp.clear();
for(;itl!=itr;++itl)
vp.push_back(pair<LL,int>(itl->v,itl->r - itl->l +1));
sort(vp.begin(),vp.end());
for(vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it){
k-=it->second;
if(k<=0)return it->first;
}
}
LL sum(int l,int r,int ex,int mod){
//询问l到r每个数字的x次方模y的和
IT itr=split(r+1),itl=split(l);
LL res=0;
for(;itl!=itr;++itl)
res=(res+(LL)(itl->r - itl->l+1)*qpow(itl->v,LL(ex),LL(mod))) %mod;
return res;
}
int n,m;
LL seed,vmax;
LL rd(){
LL ret=seed;
seed=(seed*7+13)%MOD7;
return ret;
}
LL a[MAXN];
int main(){
cin>>n>>m>>seed>>vmax;
for(int i=1;i<=n;i++){
a[i]=(rd()%vmax)+1;
s.insert(node(i,i,a[i]));
}
s.insert(node(n+1,n+1,0));
int lines=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)assign_val(l,r,LL(x));
else if(op==3)cout<<ranks(l,r,x)<<endl;
else cout<<sum(l,r,x,y)<<endl;
}
return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195702.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...