具体就是使用线段树离线操作，并利用单调栈更新的方法会被一段单调上升的序列卡为 $O(n^2 \log n)$ 的复杂度，这种方法的正确做法应该是维护历史版本和。@金爷爷哈哈 的程序在这种数据下无法跑出答案。

请求加入数据。

数据如下：

#include<bits/stdc++.h>
using namespace std;

mt19937 rnd(time(0));

int random(int l,int r){

    return rnd()%(r-l+1)+l;

}

int main(){

    freopen("data.in","w",stdout);

    int n=100000,q=100000;
    cout<<n<<" "<<q<<endl;

    for(int i=1;i<=n;i++)
        cout<<i<<" ";

    cout<<endl;

    cout<<1<<" "<<n<<endl;
    for(int i=2;i<=q;i++)
    {
        int l=random(1,n);
        int r=random(1,n);
        if(l>r) swap(l,r);
        cout<<l<<" "<<r<<endl;
    }

    return 0;

}