题解

好像是\(JSOI2018\)最简单的一道题了,但是我还是做了好久==

所有人都往一个区间走可以转化为把编号为\([l,r]\)的人按照开始位置排序,然后排名为i的人走到\(k+i-1\)的位置的花费和

这样就是\(O(nmlogn)\)的了

那考虑用数据结构来优化这个过程

首先想到能不能用所有人的位置和-\((k+k+r-l+1)*(r-l+1)/2\)

显然不能,因为有些人会往左走,有些人会往右走

但我们可以发现在\([l,r]\)中一定有一个分界点,使得这个分界点往左的人都往右走,这个分界点往右的人都往左走

那么求出这个分界点以后就可以直接算了

这个分界点要满足的条件就是\(排名为t的位置<=k+t-1\)

所以我们就可以考虑通过主席树来二分这个位置

注意一下主席树上二分的细节就可以辣

代码

#include<cstdio>#include<cstring>#include<algorithm># define LL long long# define ls (t[now].l)# define rs (t[now].r) const int M = 500005 ;const int N = 1000005 ;using namespace std ;inline int read() { char c = getchar() ; int x = 0 , w = 1 ; while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; } while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; } return x*w ;}int n , m , tot , E = 1000000 , rt[M] , ret ;struct Node { int l , r , size ; LL sum ; } t[N * 21] ;void Build(int x , int l , int r , int &now) { t[++tot] = t[now] ; now = tot ; ++t[now].size ; t[now].sum += x ; if(l == r) return ; int mid = (l + r) >> 1 ; if(mid >= x) Build(x , l , mid , ls) ; else Build(x , mid + 1 , r , rs) ;}LL qsum(int i , int j , int L , int R , int l , int r) { if(l > R || r < L) return 0 ; if(l == L && r == R) return t[j].sum - t[i].sum ; int mid = (l + r) >> 1 ; if(mid >= R) return qsum(t[i]. l ,t[j].l , L , R , l , mid) ; else if(mid < L) return qsum(t[i].r , t[j].r , L , R , mid + 1 , r) ; else return qsum(t[i].l , t[j].l , L , mid , l , mid) + qsum(t[i].r , t[j].r , mid + 1 , R , mid + 1 , r) ;}void qkth(int i , int j , int k , int l , int r , int rnk) { if(t[j].size - t[i].size == 0) return ; if(l == r) { ++ rnk ; if(l <= k + rnk - 1) ret = rnk ; return ; } int mid = (l + r) >> 1 , lsz = t[t[j].l].size - t[t[i].l].size ; if(mid <= k + rnk + lsz - 1) { ret = rnk + lsz ; qkth(t[i].r , t[j].r , k , mid + 1 , r , rnk + lsz) ; } else qkth(t[i].l , t[j].l , k , l , mid , rnk) ;}int main() { n = read() ; m = read() ; E += n ; for(int i = 1 , x ; i <= n ; i ++) { x = read() ; rt[i] = rt[i - 1] ; Build(x , 0 , E , rt[i]) ; } int idl , idr , k , l , r , mid , sz ; LL Ans = 0 ; while(m --) { idl = read() ; idr = read() ; k = read() ; ret = Ans = 0 ; sz = idr - idl + 1 ; qkth(rt[idl - 1] , rt[idr] , k , 0 , E , 0) ; Ans += 1LL * (2LL * k + ret - 1) * ret / 2 - qsum(rt[idl - 1] , rt[idr] , 0 , k + ret - 1 , 0 , E) + qsum(rt[idl - 1] , rt[idr] , k + ret , E , 0 , E) - 1LL * (2LL * k + ret + sz - 1) * (sz - ret) / 2 ; printf("%lld\n",Ans) ; } return 0 ;}