传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3289
题目大意：Mato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选 一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单 位时间内交换2个相邻的文件（因为加密需要，不能随机访问）。Mato想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？
题解：莫队+树状数组+逆序对
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 100000
using namespace std;
int n,m;
int pos[maxn],val[maxn],c[maxn],bo[maxn],ans[maxn*];
struct data{
int l,r,a,b,id;
}a[maxn*];
int read()
{
int x=; char ch; bool bo=;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') bo=;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='') ;
if (bo) return -x; return x;
}
int lowbit(int x){ return x&-x;
}
void add(int x,int v)
{
for (int i=x; i<=n; i+=lowbit(i)) c[i]+=v;
}
int query(int x)
{
int res=;
for (int i=x; i; i-=lowbit(i)) res+=c[i];
return res;
}
bool cmp(data a,data b)
{
if (pos[a.l]==pos[b.l])
if (pos[a.l]&) return a.r<b.r;
else return a.r>b.r;
return pos[a.l]<pos[b.l];
}
void init()
{
n=read(),m=read();
for (int i=; i<=n; i++) val[i]=read();
for (int i=; i<=m; i++)
{
a[i].l=read(),a[i].r=read(),a[i].a=read(),a[i].b=read(); a[i].id=i;
}
int kk=int (sqrt(n));
for (int i=; i<=n; i++) pos[i]=(i-)/kk+;
sort(a+,a++m,cmp);
}
void updata(int k,int vval)
{
if (vval==-)
{
if (bo[val[k]]==) add(val[k],-);
bo[val[k]]--;
}
else
{
if (!bo[val[k]]) add(val[k],);
bo[val[k]]++;
}
}
void work()
{
int r=,l=;
for (int i=; i<=m; i++)
{
for (; r<a[i].r; r++) updata(r+,);
for (; r>a[i].r; r--) updata(r,-);
for (; l<a[i].l; l++) updata(l,-);
for (; l>a[i].l; l--) updata(l-,);
ans[a[i].id]=query(a[i].b)-query(a[i].a-);
}
for (int i=;i<=m; i++)
printf("%d\n",ans[i]);
}
int main()
{
init();
work();
}