ODT入门_odt是什么

操作关键：推平一段区间
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::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 > vp;

IT itr = split(r+1),itl = split(l);

vp.clear();

for (; itl != itr; ++itl)

vp.push_back(pair(itl->v, itl->r - itl->l + 1));

sort(vp.begin(), vp.end());

for (vector >::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

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long long LL;

#define IT set::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
}

};

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;

}

sets;

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 >vp;

IT itr=split(r+1),itl=split(l);

vp.clear();

for(;itl!=itr;++itl)

vp.push_back(pair(itl->v,itl->r - itl->l +1));

sort(vp.begin(),vp.end());

for(vector >::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<
else cout<
}

return 0;

}

CF343D Water Tree

ODT入门_odt是什么

相关推荐