题意：很容易理解，求每次序列的顺序数
思路：要用到线段数，不然会超时，第一次处理的时候，用线段树每次来查询树的相对的位置的前几个的个数，之后交换的时候，判断用第一个交换数的大小就可以计算个数了 ，注意输出，用cout过的
#include#include #include #include using namespace std; const int MAXN = 3000005; int arr[10005],a[MAXN]; int lowbit(int x){ return x&(-x); } void update(int x,int val){ while (x < 10001){ arr[x] += val; x += lowbit(x); } } int getsum(int x){ int ans = 0; while (x > 0){ ans += arr[x]; x -= lowbit(x); } return ans; } int main(){ int x,y,n,m; long long ans; char op; while (scanf("%d",&n) != EOF){ ans = 0; memset(arr,0,sizeof(arr)); memset(a,0,sizeof(a)); for (int i = 1; i <= n; i++){ scanf("%d",&a[i]); update(a[i],1); ans += getsum(a[i]-1); } scanf("%d",&m); while (m--){ getchar(); scanf("%c",&op); if (op == 'Q') cout << ans << endl; if (op == 'R'){ scanf("%d%d",&x,&y); x++,y++; int tmp = a[x]; for (int i = x; i < y; i++){ a[i] = a[i+1]; if (a[i] > tmp) ans--; if (a[i] < tmp) ans++; } a[y] = tmp; } } } return 0; }