拼尽全力无法突破 70分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
/*#define int long long
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void write(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}*/
char buf[1<<21],*p1=buf,*p2=buf;inline int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}template <typename T>inline void redi(T& ret){ret=0;int f=1;char ch;do{ch=getc();ch=='-'?f=-1:f;}while(ch<'0'||ch>'9');while (ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+ch-48;ch=getc();}ret*=f;}template <typename T,typename... Args> inline void redi(T& t, Args&... args){redi(t);redi(args...);}char buffer[1 << 21];int p3=-1;const int p4=(1<<21)-1;inline void flush(){fwrite(buffer,1,p3+1,stdout),p3=-1;}inline void putc(const char &x){if(p3==p4)flush();buffer[++p3]=x;}template <typename T>inline void wrtn(T x){static char buf[15];static int len=-1;if(x>=0){do{buf[++len]=x%10+48,x/=10;}while(x);}else{putc('-');do{buf[++len]=-(x%10)+48,x/=10;}while(x);}while (len>=0)putc(buf[len]),--len;putc('\n');flush();}template <typename T,typename... Args> inline void wrtn(T t,Args ... args){wrtn(t);wrtn(args...);}
const int N=2e5+5;
ll a[N],ans[N];int pre[N];
mt19937 mt(time(0));
struct FHQ_treap{
    struct Tr{int wt;ll val;int ch[2],fa;}tr[N];
    struct Tag{bool rev;ll ai;}tag[N];
    int sz,rt;
    void push_up(int x){
        if(tr[x].ch[0])tr[tr[x].ch[0]].fa=x;
        if(tr[x].ch[1])tr[tr[x].ch[1]].fa=x;
        tr[x].fa=0;
    }
    int newnode(ll val){
        tr[++sz]={mt(),val,{0,0},0};
        tag[sz]={0,0};return sz;
    }
    void tagon(int x,Tag k){
        if(k.rev){
            swap(tr[x].ch[0],tr[x].ch[1]);
            tr[x].val=-tr[x].val;
            tag[x].rev^=k.rev;
            tag[x].ai*=-1;
        }
        if(k.ai){
            tr[x].val+=k.ai;
            tag[x].ai+=k.ai;
        }
    }
    void push_down(int x){
        if(tr[x].ch[0])tagon(tr[x].ch[0],tag[x]);
        if(tr[x].ch[1])tagon(tr[x].ch[1],tag[x]);
        tag[x]={0,0};
    }
    void split(int x,ll k,int &L,int &R){
        if(!x){L=R=0;return ;}
        push_down(x);
        if(tr[x].val<=k)L=x,split(tr[x].ch[1],k,tr[L].ch[1],R);
        else R=x,split(tr[x].ch[0],k,L,tr[x].ch[0]);
        push_up(x);
    }
    int merge(int x,int y){
        if(!x||!y)return x|y;
        push_down(x),push_down(y);
        push_up(x),push_up(y);
        if(tr[x].wt<tr[y].wt){
            tr[x].ch[1]=merge(tr[x].ch[1],y);
            push_up(x);return x;
        }
        else{
            tr[y].ch[0]=merge(x,tr[y].ch[0]);
            push_up(y);return y;
        }
    }
    int mergex(int x,int y){
        if(!x||!y)return x|y;
        push_down(x),push_down(y);
        if(tr[x].wt<tr[y].wt)swap(x,y);
        int yX,yY;split(y,tr[x].val,yX,yY);
        tr[x].ch[0]=mergex(tr[x].ch[0],yX);
        tr[x].ch[1]=mergex(tr[x].ch[1],yY);
        push_up(x);return x;
    }
    pair<int,int>insert(ll val){
        int x,y,w;
        split(rt,val,x,y);
        w=newnode(val);
        return {rt=merge(merge(x,w),y),w};
    }
    int update(ll k,Tag tg){
        int x,y;
        split(rt,k,x,y);
        tagon(x,tg);
        return rt=mergex(x,y);
    }
    void get_ans(int u){
        if(u==0)return;
        get_ans(tr[u].fa);
        push_down(u);
    }
}fhq;
vector<pair<ll,int>>vl[N];vector<int>vr[N];
signed main(){
    int n,q;redi(n,q);
    for(int i=1;i<=n;i++)redi(a[i]);
    for(int i=1;i<=q;i++){
        ll x;int l,r;redi(x,l,r);
        vl[l].push_back({x,i});vr[r].push_back(i);
    }
    for(int i=1;i<=n;i++){
        for(pair<ll,int> v:vl[i]){
            ll x=v.first;int id=v.second;
            pre[id]=fhq.insert(x).second;
        }
        fhq.update(a[i]>>1,{1,a[i]});
        for(int j:vr[i]){
            fhq.get_ans(pre[j]);
            ans[j]=fhq.tr[pre[j]].val;
        }
    }
    for(int i=1;i<=q;i++)wrtn(ans[i]);
    return 0;
}