莫队大法好，，分块一同乱搞。
远哥出的题，当时没做出来，今天才学会莫队。
如果[l,r] -> [l,r+1] 可以在o(1)时间内求出，就可以sqrt（n）分块后，对询问排序更新。
因为我写的太丑了，必须用输入外挂才过了。
复杂度msqrt（n）
代码：
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>#include<map>using namespace std;const int N = 1e5 +10;typedef long long ll;map<ll,ll> mm;struct quest{int l,r,id;ll ans;}p[N];int pos[N],col[N],s[N],n,m;ll ans = 0;int cmp(quest a,quest b){if(pos[a.l] == pos[b.l] ) return a.r < b.r;return a.l < b.l;}int cmp2(quest a,quest b){return a.id < b.id;}void update(int q,int x){ll c = col[q];ll t1 = mm[c-1] ,t3 = mm[c+1];mm[c] += x;ans += x*(t1+t3);}void solve(){int l,r;for(int i=1,l=1,r=0;i<=m;i++){for(;r<p[i].r;r++)update(r+1,1);for(;r>p[i].r;r–)update(r,-1);for(;l<p[i].l;l++)update(l,-1);for(;l>p[i].l;l–)update(l-1,1);p[i].ans = ans;}}void in(int &x){char ch; int minus = 0;while (ch=getchar(), (ch<'0'||ch>'9') && ch!='-');if (ch == '-') minus = 1, x = 0;else x = ch-'0';while (ch=getchar(), ch>='0'&&ch<='9') x = x*10+ch-'0';if (minus) x = -x;}void out(ll x){char hc[30];int len, minus=0;if (x<0) minus = 1, x = -x;len = 0; hc[len++] = x%10+'0';while (x/=10) hc[len++] = x%10+'0';if (minus) putchar('-');for (int i=len-1; i>=0; i–) putchar(hc[i]);}int main(){while(scanf("%d%d",&n,&m)!=EOF){ans = 0;int block = (int) sqrt(n);for(int i=1;i<=n;i++) pos[i] = i/block + 1;mm.clear();for(int i=1;i<=n;i++){int b; in(b);mm[b] = mm[b-1] = mm[b+1] = 0;col[i] = b;}//for(int i=1;i<=n;i++) printf("# %d\n",col[i]);for(int i=1;i<=m;i++){//scanf("%d%d",&p[i].l,&p[i].r);in(p[i].l); in(p[i].r);p[i].id = i;}sort(p+1,p+1+m,cmp);solve();sort(p+1,p+1+m,cmp2);for(int i=1;i<=m;i++){//printf("%lld\n",p[i].ans);out(p[i].ans);printf("\n");}}return 0;}
因为冲动会做下让自己无法挽回的事情。
