【模板】珂朵莉树（ODT）（Codeforces 896C Willem, Chtholly and Seniorious）

题意简述

维护一个数列，支持区间加，区间赋值，区间求第k小，区间求幂和

数据随机

题解思路

ODT是一种基于std::set的暴力数据结构。

每个节点对应一段区间，该区间内的数都相等。

核心操作split可以将节点拆开，修改需要的部分。

每个操作都split(r+1),split(l),再遍历其中所有区间，修改或求值。

至于时间复杂度，由assign保证

代码

#include <set>

#include <vector>

#include <utility>

#include <iostream>

#include <algorithm>

#define IT set<Node>::iterator

typedef long long ll;

using std::set; using std::vector; using std::pair;

int n,m,seed,vmax,op,l,r,x,y;

struct Node {

	int l,r;

	mutable ll v;

	Node(int L,int R,ll V):l(L),r(R),v(V) {}

	bool operator<(const Node& x) const { return l<x.l; }

};

set<Node> s;

inline int rnd() { int ret=seed; seed=(seed*7ll+13)%1000000007; return ret; }

inline int _pow(ll x,int y,const int& p,int s=1) {

	x%=p; for (;y;y>>=1,x=(ll)x*x%p) if (y&1) s=(ll)s*x%p; return s;

}

inline IT split(const int& pos) {

	IT it=s.lower_bound(Node(pos,0,0));

	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;

}

inline void assign(const int& l,const int& r,const int& va) {

	IT itr=split(r+1),itl=split(l); s.erase(itl,itr); s.insert(Node(l,r,va));

}

inline void add(const int& l,const int& r,const int& va) {

	for (IT itr=split(r+1),itl=split(l);itl!=itr;++itl) itl->v+=va;

}

inline ll q_kth(const int& l,const int& r,int k) {

	vector<pair<ll,int> > vec;

	for (IT itr=split(r+1),itl=split(l);itl!=itr;++itl) vec.push_back(pair<ll,int>(itl->v,itl->r-itl->l+1));

	std::sort(vec.begin(),vec.end());

	for (vector<pair<ll,int> >::iterator it=vec.begin();it!=vec.end();++it) {

		k-=it->second; if (k<=0) return it->first;

	}

	return -1;

}

inline int q_pwsm(const int& l,const int& r,const int& x,const int& y,int res=0) {

	for (IT itr=split(r+1),itl=split(l);itl!=itr;++itl) res=(res+1ll*_pow(itl->v,x,y)*(itl->r-itl->l+1))%y;

	return res;

}

int main() {

	std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

	std::cin>>n>>m>>seed>>vmax;

	for (register int i=1;i<=n;++i) s.insert(Node(i,i,rnd()%vmax+1));

	for (register int i=1;i<=m;++i) {

		op=rnd()%4+1; l=rnd()%n+1; r=rnd()%n+1; if (l>r) std::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) add(l,r,x);

		else if (op==2) assign(l,r,x);

		else if (op==3) std::cout<<q_kth(l,r,x)<<'\n';

		else std::cout<<q_pwsm(l,r,x,y)<<'\n';

	}

}

巴特西

【模板】珂朵莉树（ODT）（Codeforces 896C Willem, Chtholly and Seniorious）

题意简述

题解思路

代码

最新文章

热门文章