hdu_2688_Rotate(树状数组)

题意：给你n数，(n<=3e6)，有两个操作，Q为当前有多少对数，满足严格递增，R l,r为旋转l,r这个区间的数

题解：求严格递增的顺序对我们可以反向用树状数组求逆序对，300W的数据还是有点够呛，不过这里求出来也就nlogn，然后对于旋转操作，因为区间大小不超过1000，我们只需统计该区间的第一个数和后面的数的关系，如果第一个数比后面的数大，就ans++，如果小于就ans--，等于就不管，因为是严格递增，然后就是这里我加入读入优化，感觉还是没什么卵用，反而比不加快，可能我写的优化不行吧。这题卡常数卡的有点紧，要注意常数优化，还有就是HDOJ的稳定性不是很好，同一个代码有时能过，有时不能过

 1 #include<cstdio>
 2 #include<cstring>
 3 #define F(i,a,b) for(int i=a;i<=b;++i)
 4 typedef long long LL;
 5 int sum[10010],a[3000010];char op[2];
 6 
 7 inline void add(int x,int c){while(x<=10000)sum[x]+=c,x+=x&-x;}
 8 inline int ask(int x){int ans=0;while(x>0)ans+=sum[x],x-=x&-x;return ans;}
 9 
10 int main(){
11     int n,m;
12     while(~scanf("%d",&n)){
13         memset(sum,0,sizeof(sum));
14         LL ans=0;
15         F(i,0,n-1)scanf("%d",&a[i]),ans+=ask(a[i]-1),add(a[i],1);
16         scanf("%d",&m);
17         F(i,1,m){
18             scanf("%s",op);
19             if(op[0]=='Q')printf("%I64d
",ans);
20             else{
21                 int l,r;
22                 scanf("%d%d",&l,&r);
23                 int now=a[l];
24                 F(i,l+1,r){
25                     if(a[i]>now)ans--;
26                     else if(a[i]<now)ans++;
27                     a[i-1]=a[i];
28                 }
29                 a[r]=now;
30             }
31         }
32     }
33     return 0;
34 }

View Code