officeyutong

洛谷2221 高速公路

作者：

officeyutong

在

题目地址

https://www.luogu.org/problemnew/show/2221

题目:

题目描述

Y901高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。

Y901高速公路是一条由N-1段路以及N个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为1~N，从收费站i行驶到i+1(或从i+1行驶到i)需要收取Vi的费用。高速路刚建成时所有的路段都是免费的。

政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。

无聊的小A同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题:对于给定的l,r(l<r),在第l个到第r个收费站里等概率随机取出两个不同的收费站a和b，那么从a行驶到b将期望花费多少费用呢?

输入输出格式

输入格式：

第一行2个正整数N,M，表示有N个收费站，M次调整或询问

接下来M行，每行将出现以下两种形式中的一种

C l r v 表示将第l个收费站到第r个收费站之间的所有道路的通行费全部增加v

Q l r 表示对于给定的l,r，要求回答小A的问题

所有C与Q操作中保证1<=l<r<=N

输出格式：

对于每次询问操作回答一行，输出一个既约分数

若答案为整数a，输出a/1

输入输出样例

输入样例#1： 复制

4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4

输出样例#1： 复制

1/1
8/3
17/6

说明

所有C操作中的v的绝对值不超过10000

在任何时刻任意道路的费用均为不超过10000的非负整数

所有测试点的详细情况如下表所示

Test N M

1    =10    =10
2    =100    =100
3    =1000    =1000
4    =10000    =10000
5    =50000    =50000
6    =60000    =60000
7    =70000    =70000
8    =80000    =80000
9    =90000    =90000
10    =100000    =100000

这题我周六下午看了整整两节语文课，还好最后想出来了，然后发现就是线段树+一些数学技巧

这道题目可以抽象为:给定一个数列$$a_n$$,给定数列的一个子数列$$[L,R]$$,求从$$[L,R]$$中等概率的任取两点$$a,b(b>a)$$,$$sum(a,b)$$的期望.

此外 注意题目有个坑 C l r v是将[l,r]之间的道路的收费加上v

以及要注意 Q l r 查询的是两座收费站之间的值 等价于查询[l,r-1]之间道路的值

例如对于数列1 2 2 2(就是样例)

查询子数列[1,3] 就需要计算($$a_1+(a_1+a_2)+(a_1+a_2+a_3)+(a_2)+(a_2+a_3)+(a_3))/C_{3-1+1}^{2}$$

观察分子上的值 如果我们将它分成三行

$$a_1+(a_1+a_2)+(a_1+a_2+a_3)$$

$$(a_2)+(a_2+a_3)$$

$$a_3$$

我们会发现 a1只在第一行出现 出现行数为1 每行出现了3次

a2在第一行与第二行出现 出现行数为2 每行出现了2次

a3在三行都出现 出现行数为3 每行出现了1次

然后我们会发现 区间[l,r]中的每一项在分子上出现的行数+每行出现的次数恰好等于l+r

emm 至于证明 我也不会

 

然后我们就有
分子:$$\sum i {(i-l+1)*(r-i+1)*cost[i]}$$
分母:$$C_{r-l+1}^{2}=(r-l+1)*(r-l)/2$$
然后我们将分子进一步拆开可得
$$\sum {(i-l+1)*(r-i+1)*cost[i]}= (-l*r-l+r+1)*\sum cost[i]+(l+r)*\sum {i*cost[i]}-\sum i {i*i*cost[i]}$$
这样的话 我们就可以用三棵线段树 分别维护 cost[i] cost[i]*i cost[i]*i*i了
另外有几个可能会用到的数列求和公式
$$a_n=n^2$$的前缀和:$$\frac {n(n+1)(2n+1)} 6$$
 

// luogu-judger-enable-o2

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/*
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年11月10日, 下午2:54
 */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::max;
using std::min;
using std::sort;
using std::vector;
using std::map;
using std::pair;
using int_t = long long int;

int_t gcd(int_t a, int_t b) {
    if (b == 0) {
        return a;

    } else {
        return gcd(b, a % b);
    }
}
//数列an=n的前缀和

inline int_t S1(int_t n) {
    return (n * n + n) / 2;
}
//数列an=n*n的前缀和

inline int_t S2(int_t n) {
    return n * (n + 1)*(2 * n + 1) / 6;
}

class SegTree {
private:

    class SegTreeNode {
    public:
        SegTreeNode* left = nullptr;
        SegTreeNode* right = nullptr;
        int_t val = 0;
        int_t mark = 0;
        int_t begin = 0;
        int_t end = 0;
        int_t flag = 0;

        SegTreeNode(int_t begin, int_t end) :
        begin(begin), end(end) {
        }

        inline int_t length() {
            return end - begin + 1;
        }

        virtual ~SegTreeNode() {
            if (left) delete left;
            if (right) delete right;
        }

        inline void pushDown() {
            if (mark) {
                if (left) {
                    left->add(mark);
                }
                if (right) {
                    right->add(mark);
                }
                mark = 0;
            }
        }

        inline void add(int_t x) {
            mark += x;
            if (flag == 0)
                val += (end - (begin - 1)) * x;
            else if (flag == 1) {
                val += (S1(end) - S1(begin - 1)) * x;
            } else if (flag == 2) {
                val += (S2(end) - S2(begin - 1)) * x;
            }
        }
    };

    SegTree::SegTreeNode* build(int_t begin, int_t end, int_t* data, int_t flag) {
        SegTree::SegTreeNode* node = new SegTree::SegTreeNode(begin, end);
        node->flag = flag;
        if (begin == end) {
            node->val = data[begin];
            return node;
        }
        int_t mid = (begin + end) / 2;
        node->left = build(begin, mid, data, flag);
        node->right = build(mid + 1, end, data, flag);
        node->val = node->left->val + node->right->val;
        return node;
    }


public:
    SegTreeNode* root;

    virtual ~SegTree() {
        delete root;

    }

    SegTree(int_t* data, int_t begin, int_t end, int_t flag) {
        root = build(begin, end, data, flag);

    }

    int_t query(int_t begin, int_t end, SegTreeNode* curr) {
        //    cout << "querying begin " << begin << " end " << end << " at interval " << curr->begin << " " << curr->end << endl;
        if (begin > curr->end || end < curr->begin) {
            return 0;
        }
        if (begin <= curr->begin && curr->end <= end) {
            return curr->val;
        }
        curr->pushDown();
        return query(begin, end, curr->left) + query(begin, end, curr->right);
    }

    int_t modify(int_t begin, int_t end, int_t value, SegTreeNode* curr) {
        int_t result = 0;
        if (begin > curr->end || end < curr->begin) {
            return 0;
        } else if (begin <= curr->begin && curr->end <= end) {
            curr->add(value);
            result = curr->val;
        } else {
            curr->pushDown();
            modify(begin, end, value, curr->left);
            modify(begin, end, value, curr->right);
            result = curr->left->val + curr->right->val;
            
        }

        return curr->val=result;
    }


};

int_t arr[100000 + 1] = {};

/*
 需要维护
 * cost[i]
 * i*cost[i];
 * i*i*cost[i]
 * 设区间为[l,r] 则费用为
 * (-l*r-l+r+1)*Sigma[i=l->r](cost[i])
 * +(r+l)*Sigma[i=l->r](i*cost[i])
 * -Sigma[i=l->r](i*i*cost[i])
 * 
 * 区间[l,r]所能取到的对数(r-l+1)*(r-l)/2
 */
int main() {
    int_t n, m;
    cin >> n>>m;
    //维护cost[i]
    SegTree * s1 = new SegTree(arr, 1, n, 0);
    //维护i*cost[i]
    SegTree* s2 = new SegTree(arr, 1, n, 1);
    //维护i*i*cost[i]
    SegTree* s3 = new SegTree(arr, 1, n, 2);
    for (int_t i = 1; i <= m; i++) {
        char opt;
        int_t l, r;
        cin >> opt >> l>>r;
        r--;
        if (opt == 'C') {
            int_t v;
            cin>>v;
            s1->modify(l, r, v, s1->root);
            s2->modify(l, r, v, s2->root);
            s3->modify(l, r, v, s3->root);
        } else if (opt == 'Q') {
            int_t a = (-l * r - l + r + 1) * s1->query(l, r, s1->root)+(r + l) * s2->query(l, r, s2->root) - s3->query(l, r, s3->root);
            int_t b = (r + 1 - l + 1)*(r + 1 - l) / 2;
            int_t x = gcd(a, b);
            a /= x;
            b /= x;
            cout << a << "/" << b << endl;
        }
    }
    return 0;

}

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章