首页 > Web开发 > 详细

[JSOI2018]列队

时间:2019-01-19 15:59:46      阅读:150      评论:0      收藏:0      [点我收藏+]

技术分享图片

技术分享图片

题解

好像是\(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 ;
}

[JSOI2018]列队

原文:https://www.cnblogs.com/beretty/p/10291797.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!