传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3289
题目大意：Mato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选 一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单 位时间内交换2个相邻的文件（因为加密需要，不能随机访问）。Mato想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？
题解：莫队+树状数组+逆序对
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<algorithm> 6 #define maxn 100000 7 using namespace std; 8 int n,m; 9 int pos[maxn],val[maxn],c[maxn],bo[maxn],ans[maxn*10]; 10 struct data{ 11 int l,r,a,b,id; 12 }a[maxn*10]; 13 int read() 14 { 15 int x=0; char ch; bool bo=0; 16 while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') bo=1; 17 while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9') ; 18 if (bo) return -x; return x; 19 } 20 int lowbit(int x){ return x&-x; 21 } 22 void add(int x,int v) 23 { 24 for (int i=x; i<=n; i+=lowbit(i)) c[i]+=v; 25 } 26 int query(int x) 27 { 28 int res=0; 29 for (int i=x; i; i-=lowbit(i)) res+=c[i]; 30 return res; 31 } 32 bool cmp(data a,data b) 33 { 34 if (pos[a.l]==pos[b.l]) 35 if (pos[a.l]&1) return a.r<b.r; 36 else return a.r>b.r; 37 return pos[a.l]<pos[b.l]; 38 } 39 void init() 40 { 41 n=read(),m=read(); 42 for (int i=1; i<=n; i++) val[i]=read(); 43 for (int i=1; i<=m; i++) 44 { 45 a[i].l=read(),a[i].r=read(),a[i].a=read(),a[i].b=read(); a[i].id=i; 46 } 47 int kk=int (sqrt(n)); 48 for (int i=1; i<=n; i++) pos[i]=(i-1)/kk+1; 49 sort(a+1,a+1+m,cmp); 50 } 51 void updata(int k,int vval) 52 { 53 if (vval==-1) 54 { 55 if (bo[val[k]]==1) add(val[k],-1); 56 bo[val[k]]--; 57 } 58 else 59 { 60 if (!bo[val[k]]) add(val[k],1); 61 bo[val[k]]++; 62 } 63 } 64 void work() 65 { 66 int r=0,l=1; 67 for (int i=1; i<=m; i++) 68 { 69 for (; r<a[i].r; r++) updata(r+1,1); 70 for (; r>a[i].r; r--) updata(r,-1); 71 for (; l<a[i].l; l++) updata(l,-1); 72 for (; l>a[i].l; l--) updata(l-1,1); 73 ans[a[i].id]=query(a[i].b)-query(a[i].a-1); 74 } 75 for (int i=1;i<=m; i++) 76 printf("%d ",ans[i]); 77 } 78 int main() 79 { 80 init(); 81 work(); 82 }