本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：codeforces785E
正解：分块
解题报告：
考虑每次的交换，只会影响到$[l,r]$这个区间的数，那么分块维护每次的$update$操作就好了，又暴力又好写。
other：其实这道题可以转化为动态加点、动态删点的问题，然后就变成$CDQ$分治的裸题了。考虑一个经典的三维偏序问题，按修改的坐标排序之后，还要考虑权值和时间戳。树状数组维护权值，时间戳用$CDQ$分治结构，左边影响右边。维护每个时刻的变化量，最后统计一遍答案就好了。
分块：
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 200011;
int n,m,block,kcnt,a[MAXN],b[1000][2317],bel[MAXN],L[MAXN],R[MAXN];
LL ans;
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline int getpos(int x,int val){
int l=1,r=R[x]-L[x]+1,mid;
while(l<=r) {
mid=(l+r)>>1; if(b[x][mid]==val) return mid;
if(b[x][mid]>val) r=mid-1;
else l=mid+1;
}
return 0;
}
inline void modify(int x,int y){
while(y>1 && b[x][y]<b[x][y-1]){
swap(b[x][y],b[x][y-1]);
y--;
}
int lim=R[x]-L[x]+1;
while(y<lim && b[x][y]>b[x][y+1]) {
swap(b[x][y],b[x][y+1]);
y++;
}
}
inline int getans1(int x,int val){
if(b[x][1]>val) return 0;
int l=1,r=R[x]-L[x]+1,mid,pos=0;
while(l<=r) {
mid=(l+r)>>1;
if(b[x][mid]<val) pos=mid,l=mid+1;
else r=mid-1;
}
return pos;
}
inline int getans2(int x,int val){
int l=1,r=R[x]-L[x]+1,savr=r,mid,pos=r+1;
if(b[x][r]<val) return 0;
while(l<=r) {
mid=(l+r)>>1;
if(b[x][mid]>val) r=mid-1,pos=mid;
else l=mid+1;
}
return savr-pos+1;
}
inline void ck(int i,int l,int r){
if(a[i]<a[l]) ans--;
if(a[i]>a[l]) ans++;
if(a[i]<a[r]) ans++;
if(a[i]>a[r]) ans--;
}
inline void work(){
n=getint(); m=getint(); block=2300;//block=sqrt(n);
kcnt=n/block; if(n%block) kcnt++;
for(int i=1;i<=kcnt+1;i++) L[i]=n+1; ans=0;
for(int i=1;i<=n;i++) {
a[i]=i; bel[i]=(i-1)/block+1;
L[bel[i]]=min(L[bel[i]],i);
R[bel[i]]=i;
b[bel[i]][ i-L[bel[i]]+1 ]=i;
}
int l,r,x,y,bL,bR;
while(m--) {
l=getint(); r=getint(); if(l>r) swap(l,r);//!!!
if(l==r) { printf("%I64d
",ans); continue; }//!!!
bL=bel[l]; bR=bel[r];
if(bL==bR || bL==bR-1) {
for(int i=l+1;i<r;i++) ck(i,l,r);
if(bL==bR-1) {
x=getpos(bL,a[l]);
y=getpos(bR,a[r]);
b[bL][x]=a[r];
b[bR][y]=a[l];
modify(bL,x);
modify(bR,y);
}
}
else {
for(int i=bL+1;i<bR;i++) {
ans-=getans1(i,a[l]);
ans+=getans2(i,a[l]);
ans-=getans2(i,a[r]);
ans+=getans1(i,a[r]);
}
for(int i=l+1;i<=R[bL];i++) ck(i,l,r);
for(int i=L[bR];i<r;i++) ck(i,l,r);
x=getpos(bL,a[l]);
y=getpos(bR,a[r]);
b[bL][x]=a[r];
b[bR][y]=a[l];
modify(bL,x);
modify(bR,y);
}
if(a[l]>a[r]) ans--;
else ans++;
swap(a[l],a[r]);
printf("%I64d
",ans);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("785.in","r",stdin);
freopen("785.out","w",stdout);
#endif
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。