#include <bits/stdc++.h> using namespace std; #define int long long int n,q,a[100005],cnt[105],x,y,ans; //为了方便复习加上了注释 文件放电脑里不常看 所以交上来当备忘录 //整体思路：因为只改动最后一位 且ai的数据范围极其的友好 所以可以采用桶记录数字的个数 在每次修改的时候统计前面比它大的数字并相对应加减 //赛时思路是每一次修改都跑一次逆序对个数 好像还加了前缀和 但是太慢了 结束之后也没有系统性的check一遍样例或debug 分步测试和最终代码就这么混在了一块 改起来也十分的麻烦 /* 总结： 1.赛时代码要整齐 不怕多开文件 但是正式代码不能乱 2.注意观察数据范围 正解可能藏在数据范围中 不看数据范围的做法容易假 3.赛时在刚读题之后要思考多种做法的可能性 不能刚开始就死在一条路上 4.可以在文件夹里测试freopen的正确性 第一次使用freopen要注意。 5.（不是）心态！！心态！！！心态！！！赛时放弃了赛后就绝对会爆炸！！！ */ signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);//卡常 //被Br00k5xx提醒关同步流且不flush可能会输出不完整 以后学学快读 cin>>n>>q; for(int i=1;i<=n;i++){ cin>>a[i]; cnt[a[i]]++;//用桶存储数字的个数 for(int j=a[i]+1;j<=100;j++) ans+=cnt[j];//统计当前状态下前面比它大的数字（逆序对） }while(q--){//天杀的多测 cin>>x; if(x==1){//如果增加 cin>>a[++n];//输入 for(int i=a[n]+1;i<=100;i++) ans+=cnt[i];//加逆序对 cnt[a[n]]++;//加自身 }else{//如果减少 for(int i=a[n]+1;i<=100;i++) ans-=cnt[i];//减逆序对 cnt[a[n--]]--;//减自身 }cout<<ans<<'\n';//输出 }return 0; }