话不多说，直接看题：
首先我们想到冒泡排序，但是我们怎么分配这个k次消逆序对？事实上，每一个点的交换次数是一定的，比如32541，对于3，它一定要和2，1交换，即2次是固定的。
我们严谨一点，不妨对于2来说，前面有k1个比他高，后面k2个比他低，那么它至少交换k1+k2次
那么可以相等吗？
我们统计一下所有的k1,k2即为逆序对的2倍又我们可以取到2k,说明每一个人是可以取到k1+k2次。
这样子，我们就是求每一个数，统计一下它的k1,k2，然后用树状数组就愉快的AC了（注意query里N的话就超出数组范围了）。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1000099;
int h[100010],tr[N],n,sum[100010];
int lowbit(int x){
return x&(-x);
}
void add(int x,int v){
for(int i=x;i<=N;i+=lowbit(i)) tr[i]+=v;
}
int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=tr[i];
return res;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&h[i]);
for(int i=0;i<n;i++) h[i]++;
for(int i=0;i<n;i++){
sum[i]=query(N-1)-query(h[i]);
add(h[i],1);
}
memset(tr,0,sizeof(tr));
for(int i=n-1;i>=0;i--){
sum[i]+=query(h[i]-1);
add(h[i],1);
}
long long ans=0;
for(int i=0;i<n;i++) ans+=(long long)(sum[i]+1)*sum[i]/2;
cout<<ans;
}接题：
本质上就是一个扫描线的模板题。
即条形分割：
S1=（x2-x1)*h1,S2=(x3-x2)*h2......
我们用线段树维护，对于一个节点我们维护它的被覆盖的次数以及至少被覆盖一次的区间长度。
注意，这两个量都是不考虑父节点的结果
这样子，我们就可以通过+1，-1的区间操作来实现了。
特别注意，这里的Lazy标记不用下放，因为我们只要求根节点的整段区间和，所以没有必要下放。
同时维护区间化成一段段单位区间，即：
具体见下面AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n;
struct Segment
{
int x,y1,y2;
int k;
bool operator< (const Segment &t)const{
return x<t.x;
}
}seg[N*2];
struct node{
int l,r;
int cnt,len;
}tr[N*4];
void pushup(int u){
if(tr[u].cnt>0) tr[u].len=tr[u].r-tr[u].l+1;
else if(tr[u].l==tr[u].r) tr[u].len=0;
else{
tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
}
}
void build(int u,int l,int r){
tr[u]={l,r};
if(l==r) return;
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void modify(int u,int l,int r,int k){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].cnt+=k;
pushup(u);
}
else{
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify(u<<1,l,r,k);
if(r>mid) modify(u<<1|1,l,r,k);
pushup(u);
}
}
int main(){
cin>>n;
int m=0;
for(int i=0;i<n;i++){
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
seg[m++]={x1,y1,y2,1};
seg[m++]={x2,y1,y2,-1};
}
sort(seg,seg+m);
build(1,0,10000);
int res=0;
for(int i=0;i<m;i++){
if(i>0) res+=tr[1].len*(seg[i].x-seg[i-1].x);
modify(1,seg[i].y1,seg[i].y2-1,seg[i].k);
}
cout<<res;
}接下来来个三维的二分+前缀和：
一维的差分大家都熟悉，那么二维呢？
我们定义si,j为原来的矩阵，我们定bi,j=si,j-si-1,j-si,j-1+si-1,j-1;（我们定义b是为了快速根据条件修改s)
假如我们让x1,y1,x2,y2都加一个数c
那么一共4个数发生变化：
bx1,y1+=c,bx1,y2+1-=c;
bx2+1,y1-=c,bx2+1,y2+1+=c;可以看图（除4个点其他地方为0）：
求值就是前缀和即可
我们再看3维，类比一下：
s[x][y][z]=b[x][y][z]+s[x-1][y][z]+s[x][y-1][z]-s[x-1][y-1][z]+s[x][y][z-1]-s[x-1][y][z-1]-s[x][y-1][z-1]+s[x-1][y-1][z-1](可以看看魔方的结构，就是先减两旁的形体再减其下的一条线）
至于修改类比一下：有8个
b[x1][y1][z1]-=h,.....
具体见AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2000010;
int A,B,C,m;
LL s[N],b[N],bp[N];
int d[8][4]={
{0,0,0,1},//奇减偶加，从1---7的二进制
{0,0,1,-1},
{0,1,0,-1},
{0,1,1,1},
{1,0,0,-1},
{1,0,1,1},
{1,1,0,1},
{1,1,1,-1}
};
int op[N/2][7];
int get(int i,int j,int k){//三维映射
return (i*B+j)*C+k;
}
bool check(int mid){
memcpy(b,bp,sizeof(bp));
//修改
for(int i=1;i<=mid;i++){
int x1=op[i][0],x2=op[i][1],y1=op[i][2],y2=op[i][3],z1=op[i][4],z2=op[i][5],h=op[i][6];
//奇加偶减
b[get(x1,y1,z1)]-=h;
b[get(x1,y1,z2+1)]+=h;
b[get(x1,y2+1,z1)]+=h;
b[get(x1,y2+1,z2+1)]-=h;
b[get(x2+1,y1,z1)]+=h;
b[get(x2+1,y1,z2+1)]-=h;
b[get(x2+1,y2+1,z1)]-=h;
b[get(x2+1,y2+1,z2+1)]+=h;
}
memset(s,0,sizeof(s));//前缀和
for(int i=1;i<=A;i++){
for(int j=1;j<=B;j++){
for(int k=1;k<=C;k++){
s[get(i,j,k)]=b[get(i,j,k)];//除0的反转
for(int u=1;u<=7;u++){
int x=i-d[u][0],y=j-d[u][1],z=k-d[u][2],t=d[u][3];
s[get(i,j,k)]-=s[get(x,y,z)]*t;
}
if(s[get(i,j,k)]<0) return 1;
}
}
}
return 0;
}
int main(){
cin>>A>>B>>C>>m;
for(int i=1;i<=A;i++){
for(int j=1;j<=B;j++){
for(int k=1;k<=C;k++){
scanf("%lld",&s[get(i,j,k)]);
}
}
}
//初始化差分数组：
for(int i=1;i<=A;i++){
for(int j=1;j<=B;j++){
for(int k=1;k<=C;k++){
for(int u=0;u<8;u++){
int x=i-d[u][0],y=j-d[u][1],z=k-d[u][2],t=d[u][3];
bp[get(i,j,k)]+=s[get(x,y,z)]*t;
}
}
}
}
for(int i=1;i<=m;i++){
for(int j=0;j<7;j++) scanf("%d",&op[i][j]);
}
//二分
int l=1,r=m;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r;
}
