P3932 浮游大陆的68号岛

你的名字 2021-11-22 17:48 155阅读 0赞

## 题目来源：[洛谷][Link 1] ##

## 题目描述 ##

妖精仓库的储物点可以看做在一个数轴上。每一个储物点会有一些东西，同时他们之间存在距离。

每次他们会选出一个小妖精，然后剩下的人找到区间\[l,r\]\[l,r\]储物点的所有东西，清点完毕之后问她，把这个区间内所有储物点的东西运到另外一个仓库的代价是多少？

比如储物点ii有xx个东西，要运到储物点jj，代价为 x × dist(i,j)

dist就是仓库间的距离。

当然啦，由于小妖精们不会算很大的数字，因此您的答案需要对19260817取模。

## 输入输出格式 ##

输入格式：

第一行两个数表示n,m

第二行n-1个数，第i个数表示第i个储物点与第i+1个储物点的距离

第三行n个数，表示每个储物点的东西个数

之后m行每行三个数`x l r`

表示查询要把区间\[l,r\]储物点的物品全部运到储物点x的花费

输出格式：

对于每个询问输出一个数表示答案

## 输入输出样例 ##

输入样例\#1：

5 5
    2 3 4 5
    1 2 3 4 5
    1 1 5
    3 1 5
    2 3 3
    3 3 3
    1 5 5

输出样例\#1：

125
    72
    9
    0
    70

## 说明 ##

对于30%的数据，n,m≤1000

对于另外20%的数据，所有储物点间的距离都为1

对于另外20%的数据，所有储物点的物品数都为1

对于100%的数据 ,n,m≤200000;ai,bi<=2⋅10^9

解析：

这道题的取模太™扯淡了。

--------------------

这道题给出的数据明显是想让我们用前缀和优化。

作为一个明显的区间维护问题，本蒟蒻想到了线段树（因为我只学了线段树和分块 （逃）。

我们不管别的，先来看看这题具体怎么求解。

--------------------

我们先计算出距离的前缀和数组d\[\]备着，来看看费用怎么算：

1.  当l>x时，sum=w\[i\]\*(d\[i\]-d\[x\]),l<=i<=r;
2.  当r<x时，sum=w\[i\]\*(d\[x\]-d\[i\]),l<=i<=r;
3.  当l<=x<=r时，sum的值可看做前1，2种情况的合并

当我们搞定魔幻的取模，这题就过了。

我的垃圾代码：

1 #include<cstdio>
     2 #include<iostream>
     3 #define N 200010
     4 #define ll long long
     5 #define mod 19260817
     6 //能取模的地方就取模 
     7 using namespace std;
     8 ll d[N],w[N];
     9 struct segmentree{
    10     ll l,r;
    11     ll sum1,sum2;
    12 }t[N<<2];
    13 void built(ll p,ll l,ll r)
    14 {
    15     t[p].l=l;t[p].r=r;
    16     if(t[p].l==t[p].r){
    17         t[p].sum1=w[l]%mod;//根据分配率，我们可以先维护w[i]的值 ，再统一乘上d[x] 
    18         t[p].sum2=w[l]*d[l]%mod;
    19         return;
    20     }
    21     ll mid=(l+r)>>1;
    22     built(p<<1,l,mid);
    23     built(p<<1|1,mid+1,r);
    24     t[p].sum1=(t[p<<1].sum1+t[p<<1|1].sum1)%mod;
    25     t[p].sum2=(t[p<<1].sum2+t[p<<1|1].sum2)%mod;
    26 }
    27 ll ask1(ll p,ll l,ll r)
    28 {
    29     if(l<=t[p].l&&t[p].r<=r) return t[p].sum1%mod;
    30     ll mid=(t[p].l+t[p].r)>>1;
    31     ll val=0;
    32     if(l<=mid) val=(val+ask1(p<<1,l,r))%mod;
    33     if(r>mid) val=(val+ask1(p<<1|1,l,r))%mod;
    34     return val;
    35 }
    36 ll ask2(ll p,ll l,ll r)
    37 {
    38     if(l<=t[p].l&&t[p].r<=r) return t[p].sum2%mod;
    39     ll mid=(t[p].l+t[p].r)>>1;
    40     ll val=0;
    41     if(l<=mid) val=(val+ask2(p<<1,l,r))%mod;
    42     if(r>mid) val=(val+ask2(p<<1|1,l,r))%mod;
    43     return val;
    44 }
    45 int main()
    46 {
    47     ll m,n,x,l,r;
    48     scanf("%lld%lld",&n,&m);
    49     for(int i=1;i<n;i++) scanf("%lld",&d[i]);
    50     for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
    51     for(int i=1;i<n;i++) d[i]=(d[i]+d[i-1])%mod;//前缀和 
    52     for(int i=n;i>1;i--) d[i]=d[i-1];
    53     d[1]=0;
    54     built(1,1,n);
    55     while(m--)
    56     {
    57         scanf("%lld%lld%lld",&x,&l,&r);
    58         ll ans1,ans2,ans;
    59         if(l==x&&r==x){
    60             printf("0\n");
    61             continue;
    62         }
    63         if(l>x){
    64             ans=(ask2(1,l,r)-ask1(1,l,r)*d[x])%mod;//如解析所示 
    65         }
    66         if(r<x){
    67             ans=(ask1(1,l,r)*d[x]-ask2(1,l,r))%mod;
    68         }
    69         if(l<=x&&x<=r){
    70             ans1=(ask1(1,l,x-1)*d[x]-ask2(1,l,x-1))%mod;
    71             ans2=(ask2(1,x+1,r)-ask1(1,x+1,r)*d[x])%mod;
    72             ans=(ans1+ans2)%mod;
    73         }
    74         printf("%lld\n",(ans+3*mod)%mod);
    75     }
    76     return 0;
    77 }

2019-05-15 18:56:20

转载于:https://www.cnblogs.com/DarkValkyrie/p/10871397.html

[Link 1]: https://www.luogu.org/problemnew/show/P3932