一开始看错题目了，很容易看成i喜欢的中，让后写主席树区间第k大

反过来其实也很好做，我们考虑将所有的L,R,P丢到一起考虑，分两种操作，询问和修改（是不是很像cdq分治）

排个序再加上个平衡树离散化+ZKW线段树求第k大就好了

（注意题目坑点：是第k大不是第k小）

#pragma GCC optimize("O3")#pragma G++ optimize("O3")#include
    
     #include
     
      #include
      
       #define N 100010#define mid (l+r>>1)using namespace std;int n,m,t=0,ans=0;int p[N],c[N],l[N],r[N],b[N];struct op{ int o,x,y; } s[N*3];inline void input(int* s){	long long a,f,m,p;	scanf("%lld%lld%lld%lld",&a,&f,&m,&p);	s[1]=f%m; for(int i=2;i<=n;++i) s[i]=(s[i-1]*p+a+i)%m;}struct ZKW{	int n,M,s[N<<2];	void init(int T){ n=T; for(M=1;M<=n;M<<=1); --M; }	inline void insert(int x){ for(x+=M;x;x>>=1) ++s[x]; }	inline void remove(int x){ for(x+=M;x;x>>=1) --s[x]; }	inline int kth(int k){		int x;		for(x=1;x<=M;)			if(s[x<<1]>=k) x=x<<1;			else { k-=s[x<<1]; x=x<<1|1; }		return x-M;	}} T;inline bool c1(op a,op b){ return a.x
       
        
         r[i]) swap(l[i],r[i]);	}	sort(b+1,b+1+n);	m=unique(b+1,b+1+n)-b-1;	for(int i=1,j;i<=n;++i){		j=m-(lower_bound(b+1,b+1+m,c[i])-b)+1;		s[++t]=(op){
    2,p[i],i};		s[++t]=(op){
    0,l[i],j};		s[++t]=(op){
    1,r[i]+1,j};	}	reverse(b+1,b+1+m); sort(s+1,s+1+t,c1);	for(int i=1;i<=t;++i)		if(s[i].o==2) 			{ if(T.s[1]>=s[i].y) ans=(ans+b[T.kth(s[i].y)])%19921228; } 		else if(s[i].o==0) T.insert(s[i].y);		else T.remove(s[i].y);	printf("%d\n",ans);} int main(){ _18520(); }