D. Inversion Counting(思维思维思维)

思维还是不够敏锐啊…

看到这种数据范围和只需要输出奇偶就应该想到很简单的

$每次翻转区间,改变的只是区间内的逆序对$

$设原来逆序对是x,总索引对是y,反转后逆序对就是y-x$

$那么显然当y是偶数时y-x和x同奇偶$

$否则改变一次奇偶$

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int n,m,nixu; int a[maxn]; string q="even",w="odd",s; class binary_search_tree { private: int sumn[maxn]; int lowbit(int x){ return x&(-x); }; public: void insert(int x){ for(;x<=n;x+=lowbit(x) ) sumn[x]++; } int ask(int x){ int ans=0; for(;x;x-=lowbit(x) ) ans+=sumn[x]; return ans; } }bit; int main() { cin >> n; for(int i=1;i<=n;i++) { cin>>a[i]; nixu+=bit.ask(n)-bit.ask(a[i]); bit.insert(a[i]); } if(nixu%2==0) s=q; else s=w; cin>>m; for(int i=1,l,r;i<=m;i++) { cin >> l >> r; if( (r-l)*(r-l+1)/2%2==1 ) s==q?s=w:s=q; cout<<s<<endl; } }