题意

艾斯洛克是数兔结构大师，他出了一题给你做：

定义数组\(A\)的循环移位操作\(F(A)\)：将\(A\)最前面的元素移到末尾，其余元素依次往前移动。例如\(F([1,2,3,4,5])=[2,3,4,5,1]\)。

给定一个\(1 \sim N\)的排列\(P\)，接下来有\(Q\)次随机生成的操作。

每次操作给出\(L\)，\(R\)，\(K\)，将\(P[1,n]\)进行\(K\)次循环移位操作，即将\(P[1,n]\)使用函数\(F\)迭代\(K\)次。

每次操作之后，令\(A\)表示将整个排列\(P[1,n]\)经过若干次循环移位操作后，\(P[1,n]\)的逆序对数最大值，你需要求出\(P[1,n]\)至少经过多少次循环移位操作后，逆序对数能达到\(A\)。答案可以是\(0\)，即不进行任何循环移位操作。询问对原排列没有任何影响。

思路&题解

考试的时候蠢了，想的是枚举移动的距离i，然后算每次i对前i-1个数和后n-i个数的贡献，于是一道简单题都没做出来。
其实我们换个思考的方式，每次移动以后就真的移动了，把当前这第i个数当做第1个数看，那它的逆序对数肯定是\(n-2*p[i]+1\)
这样我们只要求个前缀和最大值就好！！！
随机生成操作和求前缀和最大值都可以用fhq轻松的维护

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const int N = 3e5 + 11;
int n, m;
int rt, tot;
struct node{
    int pos; LL sum, ma;
    int ls, rs; 
    int key, val, sz;
}t[N];
int read(){
    int x = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0')ch = getchar();
    while(ch >= '0' && ch <= '9')x = 10 * x + ch - 48, ch = getchar();
    return x;
}
void push_up(int x){
    if(!x)return ;
    int ls = t[x].ls, rs = t[x].rs;
    t[x].sz = t[ls].sz + t[rs].sz + 1;
    t[x].sum = t[ls].sum + t[rs].sum + t[x].val;
    LL lv = t[ls].ma;
    LL pv = t[ls].sum + t[x].val;
    LL rv = t[ls].sum + t[x].val + t[rs].ma;
    if(pv >= rv){
        t[x].pos = t[ls].sz + 1;
        t[x].ma = pv;
    }
    else t[x].pos = t[ls].sz + 1 + t[rs].pos, t[x].ma = rv;
    if(lv >= t[x].ma){
        t[x].pos = t[ls].pos;
        t[x].ma = lv;
    }
}
int merge(int x, int y){
    if(!x || !y)return x + y;
    if(t[x].key <= t[y].key){
        t[x].rs = merge(t[x].rs, y);
        push_up(x);
        return x;
    }
    else{
        t[y].ls = merge(x, t[y].ls);
        push_up(y);
        return y;
    }
}
void split(int rt, int &x, int &y, int k){
    if(!rt){
        x = y = 0;
        return ;
    }
    int ls = t[rt].ls, rs = t[rt].rs;
    if(t[ls].sz + 1 <= k){
        x = rt;
        split(rs, t[rt].rs, y, k - t[ls].sz - 1);
    }
    else{
        y = rt;
        split(ls, x, t[rt].ls, k);
    }
    push_up(x); push_up(y);
}
void insert(int x){
    int p = ++tot;
    t[p].pos = t[p].sz = 1;
    t[p].key = rand();
    t[p].ma = t[p].sum = t[p].val = x;
    rt = merge(rt, p);
}
void print(int u, int res){
    if(!u)return ;
    int ls = t[u].ls, rs = t[u].rs;
    printf("u=%d ls=%d rs=%d val=%d ma=%lld pos=%d sum=%lld i=%d\n", u, ls, rs, t[u].val, t[u].ma, t[u].pos, t[u].sum, t[ls].sz + 1 + res);
    print(ls, res);
    print(rs, res + t[ls].sz + 1);
}
int main(){
    //freopen("rabbit.in", "r", stdin);
    srand(time(0));
    t[0].ma = -1e8;
    cin>>n>>m;
    int x = 0;
    for(int i = 1;i <= n; i++){
        x = read();
        //printf("%d ", n - 2 * x + 1);
        insert(n - 2 * x + 1);
    }
    //puts("");
    //printf("ma=%lld pos=%d\n", t[rt].ma, t[rt].pos);
    //print(rt, 0);
    int l, r, k;
    while(m--){
        l = read(); r = read(); k = read();
        k %= (r - l + 1);
        if(k){
            int x, y, z, p;
            split(rt, x, y, l - 1);
            split(y, y, z, r - l + 1);
            split(y, y, p, k);
            rt = merge(x, merge(merge(p, y), z));
        }
        printf("%d\n", t[rt].ma > 0 ? t[rt].pos : 0);
    }
    return 0;
}