題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的數列，現在需要執行 $m$ 次操作，每次操作分為下列四種情況：

$1lrx$：$[l,r]$ 內的位置都加上 $x$

$2lrx$：$[l,r]$ 內的數都變為 $x$

$3lrx$：求 $[l,r]$ 內第 $x$ 小的數

$4lrxy$：求區間 $[l,r]$ 內的冪次和，對 $y$ 取模

數據隨機

題目分析：大佬博客

因為都是隨機數據，所以直接上珂朵莉樹推平就好了

有個奇怪的點是網上講解珂朵莉樹的博客都會加入一個哨兵節點，但我個人感覺是不許要加的，因為所有的運算都是針對于超尾去實現的，而 $std::set$ 顯然是自帶超尾的，所以無需加入哨兵節點防止越界

需要注意的一點細節就是 $a_i$ 可能比較大，在進行快速冪的時候需要先取模，不然會直接爆掉 $longlong$

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; struct Node {int l,r;mutable LL val;Node(int l,int r,LL val):l(l),r(r),val(val){}Node(int l):l(l){}bool operator<(const Node& t)const{return l<t.l;} }; set<Node>st; set<Node>::iterator split(int pos) {auto it=st.lower_bound(Node(pos));if(it!=st.end()&&it->l==pos) return it;it--;int l=it->l,r=it->r;LL val=it->val;st.erase(it);st.insert(Node(l,pos-1,val));return st.insert(Node(pos,r,val)).first; } void assign(int l,int r,LL val) {auto itr=split(r+1),itl=split(l);st.erase(itl,itr);st.insert(Node(l,r,val)); } void add(int l,int r,LL val) {auto itr=split(r+1),itl=split(l);for(auto it=itl;it!=itr;it++) it->val+=val; } LL kth(int l,int r,int k) {auto itr=split(r+1),itl=split(l);vector<pair<LL,int>>node;for(auto it=itl;it!=itr;it++) node.emplace_back(it->val,it->r-it->l+1);sort(node.begin(),node.end());for(auto it:node){k-=it.second;if(k<=0) return it.first;}return -1; } LL q_pow(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 query(int l,int r,int x,int mod) {auto itr=split(r+1),itl=split(l);LL ans=0;for(auto it=itl;it!=itr;it++) ans=(ans+q_pow(it->val,x,mod)*(it->r-it->l+1))%mod;return ans; } LL seed; int rnd() {int ret=seed;seed=(seed*7+13)%1000000007;return ret; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m,vmax;read(n),read(m),read(seed),read(vmax);for(int i=1;i<=n;i++){int num=rnd()%vmax+1;st.insert(Node(i,i,num));}for(int i=1;i<=m;i++){int op=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1,x,y;if(l>r) 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) write(kth(l,r,x)),putchar('\n');else if(op==4) write(query(l,r,x,y)),putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 897E Willem, Chtholly and Seniorious(珂朵莉树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。