ODT入门_odt是什么

ODT入门_odt是什么操作关键:推平一段区间cf896c题意:操作分四种,区间加上一个数、区间赋值、求区间第k小、求区间幂次和将序列中连续的相同的元素整合、用一个三元组(L,R,val)来表示set维护定义内部类:structnode{intl,r;//区间的左端点、右端点mutableLLv;//数值node(intL,intR=-1,LLV=…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

操作关键:推平一段区间
cf 896c
题意:操作分四种,
区间加上一个数、区间赋值、求区间第k小、求区间幂次和

  1. 将序列中连续的相同的元素整合、用一个三元组(L,R,val)来表示
  2. set维护
  3. 定义内部类:
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;
}

CF343D Water Tree

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195702.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • sublime3激活码[最新免费获取]

    (sublime3激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlS32PGH0SQB-eyJsaWN…

  • Java中堆和栈(java栈和堆)

    Java中堆和栈(java栈和堆)转:https://www.cnblogs.com/ibelieve618/p/6380328.htmlJAVA在程序运行时,在内存中划分5片空间进行数据的存储。分别是:1:寄存器。2:本地方法区。3:方法区。4:栈。5:堆。基本,栈stack和堆heap这两个概念很重要,不了解清楚,后面就不用学了。以下是这几天栈和堆的学习记录和心得。得些记录下来。以后有学到新的,会慢慢补充。…

  • 关于Bigdecimal比较大小

    关于Bigdecimal比较大小java中对bigdimical比较大小一般用的是bigdemical的compareTo方法;另,

  • 新手必备webstorm安装教程

    新手必备webstorm安装教程接下来我们看一下webstorm的安装1.首先下载webstrom安装包这个安装包在网上很好找点击.exe文件激活成功教程为长期有效的webstrom/IDEAlicenseserver20181.复制下方activationcode,直接粘贴在webstorm的activationcode栏上,切记先不要点ok,切记先不要点ok,切记先不要点ok,等第二步执行完…

  • css3实现光标悬浮滚动菜单

    效果:http://hovertree.com/texiao/css3/21/本文所用到的CSS知识请点击效果展示也中第一和第二个链接。代码:转自:http://hovertree.com/h/bj

    2021年12月24日
  • 5大优秀黑客必逛技术网站

    5大优秀黑客必逛技术网站5大优秀黑客必逛技术网站HackForums最理想的黑客技术学习技术根据地,也适用于开发人员游戏开发者,程序员,图形设计师以及网络营销人士HackThisSite提供合法而安全的网络安全资源,可以通过·各类挑战题目测试自己的黑客技能EnilZone一个专门面向黑科群体的论坛,其中也涉及科学,编程以及艺术等领域的内容Exploit-DB提供一整套庞大的归档体…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号