CodeForces - 896C 珂朵莉树-白红宇的个人博客

CodeForces - 896C 珂朵莉树

发布日期：2021-09-25 23:58:03 浏览次数：11 分类：技术文章

本文共 2234 字，大约阅读时间需要 7 分钟。

用set搞的比较神奇的树吧，玄学时间复杂度，代码简洁好写，无聊学了用来水题再好不过了 ~ ~ ~

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pair#define IT set
               
                ::iteratorusing namespace std;typedef long long LL;typedef pair
                
                  PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;LL seed,vmax;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
                 
                  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 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));}void add(int l,int r,LL val)//区间加{ IT itr=split(r+1),itl=split(l); for(;itl!=itr;++itl) itl->v+=val;}LL ran(int l,int r,int k)//区间第k小{ vector
                  
                   
                     >v; IT itr=split(r+1),itl=split(l); for(;itl!=itr;itl++) v.pb({ itl->v,itl->r-itl->l+1}); sort(v.begin(),v.end()); for(vector
                    
                     
                       >::iterator it=v.begin();it!=v.end();it++) { k-=it->second; if(k<=0) return it->first; }}LL qmi(LL a,LL b,LL mod){ LL ans=1; a%=mod; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans;}LL sum(int l,int r,int ex,int mod)//区间幂次和{ IT itr=split(r+1),itl=split(l); LL ans=0; for(;itl!=itr;itl++) ans=(ans+(LL)((itl->r-itl->l+1)%mod)*qmi(itl->v,LL(ex),LL(mod))%mod)%mod; return ans%mod;}LL rad(){ LL ret=seed; seed=(seed*7+13)%1000000007; return ret;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); cin>>n>>m>>seed>>vmax; for(int i=1;i<=n;i++) { LL x=(rad()%vmax)+1; s.insert(node(i,i,x)); } s.insert(node(n+1,n+1,0)); for(int i=1;i<=m;i++) { int op=(rad()%4)+1; int l=(rad()%n)+1; int r=(rad()%n)+1; if(l>r) swap(l,r); int x,y; if(op==3) x=(rad()%(r-l+1))+1; else x=(rad()%vmax)+1; if(op==4) y=(rad()%vmax)+1; if(op==1) add(l,r,1ll*x); else if(op==2) assign_val(l,r,1ll*x); else if(op==3) printf("%lld\n",ran(l,r,1ll*x)); else printf("%lld\n",sum(l,r,x,y)); } return 0;}/**/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/108288644 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Vases and Flowers HDU - 4614 线段树 + 二分

下一篇：P4513 小白逛公园线段树

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章