LYK loves music

Description

LYK喜欢听音乐，它的歌单里共有n首音乐，而且它每次听音乐时都是连续地听m首，
它甚至能记得自己给每首音乐的评分ai。
现在它想选择一首歌开始听，使得接下来连续m首歌的评分 当然它最开始听的歌也是需要在一段区间[li,ri]内选择的。
现在它想让你帮它挑选一首最开始听的歌，使得以这首歌开始的连续m首歌中，评分

Input

第一行输入2个数n,m。
接下来一行n个数ai表示第i首歌的评分。
接下来一行一个Q，表示有Q次询问。
接下来Q行，每行3个数li,ri,qi。为了体现询问的在线性，对于该询问，xi=ans{i-1}^qi。
其中^表示异或，ans{i-1}表示上一问的答案，若i=1，则ans{i-1}=0。
n,Q<=200000。
1<=li<=ri<=n-m+1,0<=ai,qi<2^30,1<=m<=n

Output

Q行，表示评分

Solution:

我们发现m是固定的，考虑以这一点为突破口

我们先考虑离线怎么来做，对于所有询问的\(q_i\)，我们先把它从小到大排序

考虑对于每一个点，当它有贡献时，他会影响的左端点是一段连续的区间\([max(1,i-m+1),i]\)

那么我们把\(a\)数组按从小到大排序，用线段树来维护这个贡献，每次操作即为区间加，区间最小值，时间复杂度\(O(n\,log \, n)\)

那么在线怎么做呢，事实上，如果是在线，那么我们建一颗主席树，预处理好操作，每次找到对应的\(rt\)查询即可

Code:

#include
using namespace std;
const int N=2e5+11;
int n,m,Q,cnt,lstans,rt[N];
struct Pos{int id,v;}a[N];
struct Seg{int l,r,t,v;}tr[N*50];
inline bool cmp(Pos x,Pos y){return x.vR) return ;
    q=++cnt;give(q,p);
    int mid=l+r>>1;
    if(l>=L&&r<=R) tr[q].t+=v;
    else ins(ls,Ls,l,mid,L,R,v),ins(rs,Rs,mid+1,r,L,R,v);
    update(q);
}
int query(int q,int l,int r,int L,int R){
    if(l>=L&&r<=R) return tr[q].v;
    int mid=l+r>>1,re=N;
    if(mid>=L) re=min(re,query(ls,l,mid,L,R));
    if(mid>1;
        if(a[mid].v