/*    题目大意：给出每头奶牛的位置和至少要多少分贝的音量才能听到谈话    现在求奶牛两两交流成功需要的距离*分贝的总和。    题解：我们将奶牛对于需要的分贝排序，那么在计算的时候，    每头奶牛只要计算和序列前面所有奶牛的答案即可    那么只要维护前面所有奶牛和其距离之差的绝对值之和即可    将其拆分为坐标小于该奶牛的坐标之和，和大于该奶牛的部分    发现只要用线段树维护区间和和区间数的个数即可。*/#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int N=20010;int T[N*4],C[N*4],n,t,c,M;struct data{int v,x;}p[N];long long ans;bool cmp(data a,data b){return a.v<b.v;}void add(int x,int y){    T[x+=M]+=y; C[x]++;    for(x/=2;x;x/=2){        T[x]=T[x<<1]+T[(x<<1)^1];        C[x]=C[x<<1]+C[(x<<1)^1];    }}void query(int x,int y){    t=c=0;    x+=M-1;y+=M+1;     while(x^y^1>0){         if(~x&1)t+=T[x+1],c+=C[x+1];         if(y&1)t+=T[y-1],c+=C[y-1];         x>>=1;y>>=1;     }}int main(){    for(M=1;M<N;M<<=1);    while(~scanf("%d",&n)){        for(int i=1;i<=n;i++)scanf("%d%d",&p[i].v,&p[i].x);        sort(p+1,p+n+1,cmp);        memset(T,0,sizeof(T));        memset(C,0,sizeof(C));        for(int i=1;i<=n;i++){            query(1,p[i].x);            ans+=1LL*p[i].v*(p[i].x*c-t);            query(p[i].x,20000);            ans+=1LL*p[i].v*(t-p[i].x*c);            add(p[i].x,p[i].x);        }printf("%lld\n",ans);    }return 0;}

/*    题目大意：在一个棋盘上放满白子，现在把一些白子变成黑子，    如果一个白子上下左右都有黑子，就会变成黑子，问最终黑子个数    题解：首先我们在每列的开头和结尾做标记，之后对行线扫描，    如果是列的开头，那么在该列中标记，如果是列的结尾，则在该列中去除标记    那么我们只要统计行的开头到行的结尾之间夹着多少列标记，且该列下该行没有原来的黑子    就是该行新增的黑子数量，对于总的黑子数量，可以用树状数组统计，之后容斥一下列标记即可。*/#include <cstdio>#include <algorithm>#include <utility>#define cx first#define cy secondusing namespace std;typedef long long LL; const int MAX_N=100010;typedef pair<int,int> P;int t,c[MAX_N],r[MAX_N],N,ys[MAX_N],d[MAX_N],vis[MAX_N];P p[MAX_N];bool cmp(int a,int b){return p[a].cy<p[b].cy||p[a].cy==p[b].cy&&p[a].cx<p[b].cx;}int sum(int x){int s=0;while(x)s+=c[x],x-=(x&-x);return s;}void add(int x,int v){while(x<=t)c[x]+=v,x+=x&-x;}int main(){    scanf("%d",&N);    for(int i=0;i<N;i++)scanf("%d%d",&p[i].cx,&p[i].cy),r[i]=i;    sort(p,p+N); sort(r,r+N,cmp);    ys[r[0]]=1; d[r[0]]=1;    for(int i=1;i<N;i++){        ys[r[i]]=ys[r[i-1]];        if(p[r[i]].cy==p[r[i-1]].cy)continue;        d[r[i-1]]--; d[r[i]]++;        ys[r[i]]++;    }LL ans=N; d[r[N-1]]--; t=ys[r[N-1]];    for(int i=0,j=0;i<N;){        for(j=i;j<N&&p[j].cx==p[i].cx;j++)            if(d[j]<0){vis[ys[j]]=0;add(ys[j],-1);}        if(ys[i]<ys[j-1]-1){            ans+=sum(ys[j-1]-1)-sum(ys[i]);            for(int k=i+1;k<j-1;k++)if(vis[ys[k]])ans--;        }for(;i<j;i++)if(d[i]>0){add(ys[i],1);vis[ys[i]]=1;}    }printf("%lld\n",ans);    return 0;}

/*    题目大意：要求维护两个操作，矩阵翻转和单点查询    题解：树状数组可以处理前缀和问题，前缀之间进行容斥即可得到答案。*/#include <cstring>#include <cstdio>const int N=1010;using namespace std;int c[N][N],n,m,T;char op[2];void add(int x,int y){    int i,j,k;    for(i=x;i<N;i+=i&-i)    for(j=y;j<N;j+=j&-j)    c[i][j]^=1;}int sum(int x,int y){    int i,j,ret=0;    for(i=x;i;i-=i&-i)    for(j=y;j;j-=j&-j)    ret^=c[i][j];    return ret;}int main(){    scanf("%d",&T);    for(int cas=0;cas<T;cas++){        if(cas)puts("");        memset(c,0,sizeof(c));        scanf("%d%d",&n,&m);        while(m--){            int x,y,x1,y1;            scanf("%s%d%d",op,&x,&y);            if(op[0]==‘Q‘)printf("%d\n",sum(x,y));            else{                scanf("%d%d",&x1,&y1);                add(x,y); add(x1+1,y);                add(x,y1+1); add(x1+1,y1+1);            }        }    }return 0;}

/*    题目大意：一些人站成一个圈，每个人手上都有一个数字，    指定从一个人开始淘汰，每次一个人淘汰时，将手心里写着的数字x展示    如果x是正数，则淘汰右手边第x个人，否则淘汰左手边地-x个人。    每个人淘汰的时候将获得积分，积分的多少取决于他是第几个淘汰的，    积分为淘汰的顺序数拥有的因子数量    输出积分最高的人和其积分    题解：首先，我们计算出第几个淘汰的人分数最高，那么我们只要模拟到这个人淘汰即可    在处理中，寻找下一个人时我们可以用线段树求kth的方法求出这个人的位置，顺序处理即可。*/#include <cstdio>#include <cstring> using namespace std;const int N=500010;int n,k,T[N*4],m,id,ans[N];struct data{int val;char name[20];}p[N];void build(int x,int l,int r){    T[x]=r-l+1;    if(l==r)return;    int mid=(l+r)>>1;    build(x<<1,l,mid);    build(x<<1|1,mid+1,r);}int update(int key,int x,int l,int r){    T[x]--; if(l==r)return l;    int mid=(l+r)>>1;    if(T[x<<1]>=key)return update(key,x<<1,l,mid);    return update(key-T[x<<1],x<<1|1,mid+1,r);}void GetID(){       memset(ans,0,sizeof(ans));    for(int i=1;i<=n;i++){        for(int j=i;j<=n;j+=i)ans[j]++;    }int mx=ans[id=1];    for(int i=2;i<=n;i++)if(ans[i]>mx){mx=ans[i];id=i;}}int main(){    while(~scanf("%d%d",&n,&k)){        build(1,1,n); GetID();        for(int i=1;i<=n;i++)scanf("%s%d",p[i].name,&p[i].val);        int mod=T[1],pos=0;        p[0].val=0; m=id;        while(m--){            if(p[pos].val>0)k=((k-1+p[pos].val-1)%mod+mod)%mod+1;            else k=((k-1+p[pos].val)%mod+mod)%mod+1;            pos=update(k,1,1,n); mod=T[1];        }printf("%s %d\n",p[pos].name,ans[id]);    }}

/*    题目大意：求区间最大值和最小值的差值    题解：线段树维护区间极值即可。*/#include <cstdio>#include <algorithm>#include <cstring> #include <climits>using namespace std;const int N=1000010;int T[N*4],C[N*4],n,M,m;struct data{int v,x;}p[N];long long ans;bool cmp(data a,data b){return a.v<b.v;}void add(int x,int y){    T[x+=M]=y; C[x]=y;    for(x/=2;x;x/=2){        T[x]=max(T[x<<1],T[(x<<1)^1]);        C[x]=min(C[x<<1],C[(x<<1)^1]);    }}int query(int x,int y){    int t=INT_MIN,c=INT_MAX;    x+=M-1;y+=M+1;     while(x^y^1>0){         if(~x&1)t=max(T[x+1],t),c=min(C[x+1],c);         if(y&1)t=max(T[y-1],t),c=min(C[y-1],c);         x>>=1;y>>=1;     }return t-c;}int main(){    scanf("%d%d",&n,&m);    for(M=1;M<n;M<<=1);    for(int i=0;i<=M+n;i++)C[i]=INT_MAX,T[i]=INT_MIN;    for(int i=1;i<=n;i++){        int x; scanf("%d",&x);        add(i,x);     }    while(m--){        int l,r; scanf("%d%d",&l,&r);        printf("%d\n",query(l,r));    }return 0;}

/*    题目大意：有一个有序序列，要求区间查询出现次数最多的数    题解：维护每个区间左端点和右端点，以及左右的长度，还有区间的答案    每次线段合并的时候，对区间数据进行合并即可。*/#include <cstdio>#include <algorithm>using namespace std;const int N=100010;struct data{int a,b,l,r,val;}T[N*4];int num[N],n,q,l,r;data combine(data &l,data &r){	  data ans;     ans.a=l.a; ans.b=r.b;    ans.l=l.a==r.a?l.l+r.l:l.l;    ans.r=r.b==l.b?l.r+r.r:r.r;    ans.val=max(l.val,r.val);    if(l.b==r.a)ans.val=max(ans.val,l.r+r.l);    return ans;}void build(int x,int l,int r){    if(l==r){T[x]=(data){num[l],num[r],1,1,1};return;}    int mid=(l+r)>>1;    build(x<<1,l,mid);build(x<<1|1,mid+1,r);    T[x]=combine(T[x<<1],T[x<<1|1]);}data query(int L,int R,int x,int l,int r){    if(r<L||R<l){data u;return u;}    if(L<=l&&r<=R)return T[x];    int mid=(l+r)>>1;    data vl=query(L,R,x<<1,l,mid),vr=query(L,R,x<<1|1,mid+1,r);    if(mid<L)return vr;    if(mid>=R)return vl;    return combine(vl,vr);}int main(){    while(scanf("%d",&n)&&n){        scanf("%d",&q);        for(int i=1;i<=n;i++)scanf("%d",&num[i]);        build(1,1,n);        while(q--){            scanf("%d%d",&l,&r);            printf("%d\n",query(l,r,1,1,n).val);        }    }return 0;}

/*    题目大意：给出几面墙，均垂直于x轴或者y轴，给出一些鸟的位置（二维坐标点），    鸟只会垂直x轴或者y轴飞行，并且会撞上最近的墙，问每面墙最后会有几只鸟撞上去。    题解：我们将所有的二维坐标离散，对xy方向分别进行扫描线，    以y轴方向为例，我们先从y最小的线开始扫，    如果是墙，那么在线段树中更新其在x轴上的分布位置    如果是鸟的坐标，那么在线段树中查找其位置，更新其答案。    之后从y最大的开始反向扫描，更新，x方向也同理。*/#include <cstdio>#include <algorithm> #include <cstring>#include <climits>using namespace std;const int N=50010;int n,m,wall,tot,dis[N],v[N],w[N],T[10*N],*arr;int x[3*N],y[3*N],ry[3*N],rx[3*N],r[3*N],xs[3*N],ys[3*N],px[3*N],py[3*N];bool cmp(int a,int b){return arr[a]<arr[b];}void compress(int *x,int *r,int n,int *a,int *mp){    for(int i=0;i<n;i++)r[i]=i;     arr=x; sort(r,r+n,cmp);    int m=-1; a[r[0]]=++m; mp[m]=x[r[0]];    for(int i=1;i<n;i++){        int cur=r[i],lst=r[i-1];        if(x[cur]==x[lst])a[cur]=m;        else a[cur]=++m,mp[m]=x[cur];    }}int query(int q,int x,int l,int r){    if(T[x]!=-2)return T[x];    int mid=(l+r)>>1;    if(q<mid)return query(q,x<<1|1,l,mid);    return query(q,x+1<<1,mid,r);}void update(int a,int b,int x,int l,int r,int val){    if(r<=a||b<=l)return;    else if(a<=l&&r<=b)T[x]=val;    else{        if(T[x]!=-2){            T[x+1<<1]=T[x<<1|1]=T[x];            T[x]=-2;        }int mid=(l+r)>>1;        update(a,b,x<<1|1,l,mid,val);         update(a,b,x+1<<1,mid,r,val);    }}void scan(int k,int *ys,int *xs,int *py,int W){    if(k<wall){        int _k=k^1;        if(xs[_k]>=xs[k])update(xs[k],xs[_k]+1,0,0,W,k/2);     }else{        int t=query(xs[k],0,0,W);        if(~t){            int d=min(abs(py[ys[k]]-py[ys[t*2]]),abs(py[ys[k]]-py[ys[t*2+1]]));            k-=wall; if(d<dis[k])dis[k]=d,v[k]=t;        }    }}void fly(int *ry,int *ys,int *xs,int *py,int W){    T[0]=-1; for(int i=0;i<tot;i++)scan(ry[i],ys,xs,py,W);    T[0]=-1; for(int i=tot-1;i>=0;i--)scan(ry[i],ys,xs,py,W); }int main(){    scanf("%d%d",&n,&m);    wall=2*n; tot=wall+m;    for(int i=0;i<tot;i++)scanf("%d%d",x+i,y+i);    compress(x,rx,tot,xs,px);    compress(y,ry,tot,ys,py);    fill(dis,dis+m,INT_MAX);memset(w,0,n);    fly(ry,ys,xs,py,xs[rx[tot-1]]+1);    fly(rx,xs,ys,px,ys[ry[tot-1]]+1);    for(int i=0;i<m;i++)++w[v[i]];    for(int i=0;i<n;i++)printf("%d\n",w[i]);    return 0;}

/*    题目大意：告诉你一个区间至少要选定的数字的个数，给出n个区间的需求    问最少选取几个数字可以满足所有的需求    题解：对于区间[a,b]建立不等式Sb+1-Sa>=c，最后要求最小化Smax，    结合基础条件Si+1-Si>=0,Si-Si+1>=-1,构造差分约束系统求最长路就是答案。*/#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=200010,inf=~0U>>2,M=200000;int time[N],q[N],size,h,t,n,ed,dis[N],in[N],nxt[N],w[N],v[N],g[N],ma,mi,u,e,cost;void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}int spfa(int S){    for(int i=0;i<=n;i++)dis[i]=-inf,in[i]=0,time[i]=0;    time[S]=1,dis[S]=0,in[S]=1;    int i,x,size; q[h=t=size=1]=S;    while(size){        for(i=g[x=q[h]],h=(h+1)%M,size--;i!=-1;i=nxt[i])if(dis[x]+w[i]>dis[v[i]]){            dis[v[i]]=dis[x]+w[i];            if(!in[v[i]]){                time[v[i]]++,t=(t+1)%M,size++,in[q[t]=v[i]]=1;                if(time[v[i]]>n)return -1;            }        }in[x]=0;    }if(dis[n]==-inf)return -2;    return dis[n];}int main(){    while(~scanf("%d",&n)){        ed=0;memset(g,-1,sizeof(g));        ma=-inf; mi=inf;        for(int i=1;i<=n;i++){            scanf("%d%d%d",&u,&e,&cost);            add(u,e+1,cost);            ma=max(e+1,ma); mi=min(u,mi);        }for(int i=mi;i<ma;i++)add(i,i+1,0),add(i+1,i,-1);         n=ma; printf("%d\n",spfa(mi));    }return 0;}

/*    题目大意：给出一个数列，每次删去一个数，求一个数删去之前整个数列的逆序对数。    题解：一开始可以用树状数组统计出现的逆序对数量    对于每个删去的数，我们可以用线段树求出它在原序列中的逆序对贡献    在线段树的每个区间有序化数据，就可以二分查找出这个数在每个区间的位置，    这样就处理出了划分出的区间的贡献，先用答案减去这一部分    接下来考虑已经删去部分的容斥，我们发现只要对删去部分再做一次类似的操作，    将这一部分跟当前删去数求一次贡献就是刚才多减去的部分，将这部分的答案再加回去。    这个可以在线段树上查找的同时用树状数组维护。    这样子就能处理每一次的删数操作了。*/#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=200010;int n,m,c[30][N],a[30][N],arr[N],id[N];long long ans;void add(int c[],int x,int v,int n){while(x<=n)c[x]+=v,x+=x&-x;}int sum(int c[],int x,int n=0){int s=0;while(x>n)s+=c[x],x-=x&-x;return s;}void build(int x,int l,int r,int d){    int mid=(l+r)>>1;    for(int i=l;i<=r;i++)a[d][i]=a[d-1][i],c[d][i]=0;    if(l==r)return;    build(x<<1,l,mid,d+1);    build(x<<1|1,mid+1,r,d+1);    sort(a[d]+l,a[d]+r+1);}int find(int L,int R,int d,int v){    int l=L,r=R;    while(l<r){        int mid=(l+r)>>1;        if(a[d][mid]>=v)r=mid;        else l=mid+1;    }if(a[d][l]>v)l--;    return l;}void query(int x,int l,int r,int L,int R,int v,int d,int f){    int mid=(l+r)>>1;    if(L<=l&&r<=R){        int k=find(l,r,d,v),t=sum(c[d],k,l-1);        if(!f){k=r-k;t=sum(c[d],r,l-1)-t;}        else k-=l-1;        ans-=k-t; return;    }if(l>=r)return;    if(L<=mid)query(x<<1,l,mid,L,R,v,d+1,f);    if(R>mid)query(x<<1|1,mid+1,r,L,R,v,d+1,f);}void update(int x,int l,int r,int s,int v,int d){    int mid=(l+r)>>1;    if(l==r){add(c[d],l,1,r);return;}    if(l>=r)return;    if(s<=mid)update(x<<1,l,mid,s,v,d+1);    else update(x<<1|1,mid+1,r,s,v,d+1);    int k=find(l,r,d,v);    add(c[d],k,1,r);}int main(){    while(~scanf("%d%d",&n,&m)){        ans=0; memset(arr,0,sizeof(arr));        for(int i=1;i<=n;i++){            scanf("%d",&a[0][i]); id[a[0][i]]=i;            ans+=i-1-sum(arr,a[0][i]);            add(arr,a[0][i],1,n);        }build(1,1,n,1);        while(m--){            int k;            scanf("%d",&k);            printf("%lld\n",ans);            if(ans){                query(1,1,n,1,id[k]-1,k,1,0);                query(1,1,n,id[k]+1,n,k,1,1);                update(1,1,n,id[k],k,1);            }        }    }return 0;}