正文

ural1855tradeguildsoferathia

mxzf0213  mxzf0213  2022-08-05  307

关键词：

Trade Guilds of Erathia

Time limit: 2.0 second
Memory limit: 64 MB

The continent of Antagarich was colonized slowly. Long ago its northern part was inhabited by the elves of Avlee. Later, the hot southern desert of Bracada was occupied by the white mages. At the same time, necromancers settled in Deyja, a land to the north of Bracada and to the south-west of Avlee. Although white and dark mages didn‘t really like each other, each group had some artifacts that the other group would be happy to buy. As a result, the trading relationship between Bracada and Deyja grew stronger, and soon the mages built a very busy trade route between these lands.

Erathia was founded later, and at first it was stretched along this route. At that time Erathia‘s economy was based solely on trading, so new trading guilds appeared all the time. Each of the guilds was present in a few cities which were consecutively situated along the route. Caravans of each guild travelled between all pairs of cities of that guild equally often.

The state‘s treasury was replenished by fees collected from all the caravans moving along the trade route. There was a fee for each route segment connecting two neighboring cities, and this fee could change over time. For example, the fee could be decreased in the areas of frequent goblin attacks, or increased in the areas with high traffic.

Loins, the royal treasurer, studies Erathia‘s economy and tries to predict the profit of trade guilds. He wants to know the amount of money paid in fees by each guild. He has a chronologically ordered list of documents that contains all the royal orders changing the fee and all the papers establishing new guilds. This data should be used to calculate the average fee paid by a caravan of a given trade guild.

Input

The first line contains the number n of cities in Erathia and the number m of documents collected by Loins (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The following m lines describe the documents of two possible types:

“change a b d”: the fee for travelling along each route segment between cities a and bchanged by d gold coins (if d is positive, the fee increased; if d is negative, the fee decreased);
“establish a b”: a new guild which is present in all cities between a and b was established.

All numbers are integers; 1 ≤ a < b ≤ n; −10 000 ≤ d ≤ 10 000. Cities are numbered in the order they are located along the route: from Bracada to Deyja. The fee for travelling along a segment was never larger than 10 000 gold coins, otherwise merchants would protest. Of course, the fee was always non-negative. Before the first royal order changing the fee, it is equal to zero for all route segments.

Output

After each document establishing the new guild, output in a single line the average amount of fee paid by a caravan of this guild. The absolute or relative error should not exceed 10−6.

Sample

input	output
4 5 change 1 4 2 change 1 2 -1 establish 1 2 establish 2 4 establish 1 4	1.00000000 2.66666667 2.83333333

input

output

4 5
change 1 4 2
change 1 2 -1
establish 1 2
establish 2 4
establish 1 4

1.00000000
2.66666667
2.83333333

分析：设询问区间为[l,r],第k条路编号为k+1;

　　　则第k条路的贡献为(k-l)*(r-k+1)*cost[k]；

　　　展开后即[-k*k+(l+1+r)*k-l-l*r]*cost[k]；

　　　线段树单点维护好cost[k],k*cost[k],k*k*cost[k]即可；

　　　注意爆int；

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=1e5+10;
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,m,k;
char op[10];
ll ans[3];
ll gao(int p)
{
    return (ll)p*(p+1)*(2*p+1)/6;
}
struct Node
{
    ll sum,sum1,sum2,lazy;
} T[maxn<<2];

void PushUp(int rt)
{
    T[rt].sum = T[rt<<1].sum + T[rt<<1|1].sum;
    T[rt].sum1 = T[rt<<1].sum1 + T[rt<<1|1].sum1;
    T[rt].sum2 = T[rt<<1].sum2 + T[rt<<1|1].sum2;
}

void PushDown(int L, int R, int rt)
{
    int mid = (L + R) >> 1;
    ll t = T[rt].lazy;

    T[rt<<1].sum += t * (mid - L + 1);
    T[rt<<1|1].sum += t * (R - mid);

    T[rt<<1].sum1 += t * (mid - L + 1)*(mid + L)/2;
    T[rt<<1|1].sum1 += t * (R - mid)*(R + mid +1)/2;

    T[rt<<1].sum2 += t * (gao(mid)-gao(L-1));
    T[rt<<1|1].sum2 += t * (gao(R)-gao(mid));

    T[rt<<1].lazy += t;
    T[rt<<1|1].lazy += t;
    T[rt].lazy = 0;
}

void Update(int l, int r, ll v, int L, int R, int rt)
{
    if(l==L && r==R)
    {
        T[rt].lazy += v;
        T[rt].sum += v * (R - L + 1);
        T[rt].sum1 += v * (R - L + 1)*(R + L)/2;
        T[rt].sum2 += v * (gao(R)-gao(L-1));
        return ;
    }
    int mid = (L + R) >> 1;
    if(T[rt].lazy) PushDown(L, R, rt);
    if(r <= mid) Update(l, r, v, Lson);
    else if(l > mid) Update(l, r, v, Rson);
    else
    {
        Update(l, mid, v, Lson);
        Update(mid+1, r, v, Rson);
    }
    PushUp(rt);
}

void Query(int l, int r, int L, int R, int rt)
{
    if(l==L && r== R)
    {
        ans[0]+=T[rt].sum;
        ans[1]+=T[rt].sum1;
        ans[2]+=T[rt].sum2;
        return;
    }
    int mid = (L + R) >> 1;
    if(T[rt].lazy) PushDown(L, R, rt);
    if(r <= mid) Query(l, r, Lson);
    else if(l > mid) Query(l, r, Rson);
    else Query(l, mid, Lson) , Query(mid + 1, r, Rson);
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b,c;
        scanf("%s",op);
        if(op[0]==‘c‘)
        {
            scanf("%d%d%d",&a,&b,&c);
            Update(a+1,b,(ll)c,1,n,1);
        }
        else
        {
            scanf("%d%d",&a,&b);
            ans[0]=ans[1]=ans[2]=0;
            Query(a+1,b,1,n,1);
            printf("%.10f
",(double)(-ans[2]+(a+b+1)*ans[1]-(a+(ll)a*b)*ans[0])/(b-a)/(b-a+1)*2);
        }
    }
    //system("Pause");
    return 0;
}

1855:[scoi2010]股票交易[单调队列优化dp]

1855:[Scoi2010]股票交易TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 1083 Solved: 519[Submit][Status][Discuss]Description最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。通查看详情

●bzoj1855[scoi2010]股票交易

题链：http://www.lydsy.com/JudgeOnline/problem.php?id=1855题解：DP,单调队列优化。（好久没做DP题，居然还意外地想出来了）定义dp[i][k]表示前i天，手上还有k股的最大收益。（注意这个定义是个前缀的形式）假设枚举到了第i天，令j=i-W-1。... 查看详情

bzoj1855:[scoi2010]股票交易

题面BzojSol设(f[i][j])表示第(i)天有(j)张股票的最大收益转移很简单辣#include<bits/stdc++.h>#defineRGregister#defineILinline#defineFill(a,b)memset(a,b,sizeof(a))usingnamespacestd;typedeflonglongll;constint_(2010); 查看详情

html1855mm_top_promo.html(代码片段)

查看详情

洛谷p1855榨取kkksc03题解

...正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=1855题目描述洛谷的运营组决定，如果一名oier向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有20个或以上的成员，上传10道以上的私有题目，布置过... 查看详情

bzoj1855[scoi2010]股票交易(代码片段)

...本篇将讲述如何借助单调队列优化dp。我先丢一道题：bzoj1855 此题不难想出O(n^4)做法，我们用f[i][j]表示第i天手中持有j只股票时，所赚钱的最大值。不难推出以下式子：$f[i][j]=max\left\\beginalignedf[k][l]+(l-j)\timesbs[i],l\in[j,j+bs[i]]\\f... 查看详情

bzoj1855dp+单调队列优化(代码片段)

思路：很容易写出dp方程，很容易看出能用单调队列优化。。#include<bits/stdc++.h>#defineLLlonglong#definefifirst#definesesecond#definemkmake_pair#definePIIpair<int,int>#definey1skldjfskldjg#definey2skldfjsklejgusingnam 查看详情

bzoj1855[scoi2010]股票交易dp+单调队列

【BZOJ1855】[Scoi2010]股票交易Description最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i... 查看详情

bzoj1855[scoi2010]股票交易单调队列优化dp

题目链接BZOJ1855题解设$f[i][j]$表示第$i$天结束时拥有$j$张股票时的最大收益若$i\leW$，显然在这之前不可能有交易\[f[i][j]=max\f[i-1][j],-ap[i]*j\\quad[j\leas[i]]\]否则，就有三种选择：①购买\[f[i][j]=max\f[i-W-1][k]-ap[i]*(j-k)\\quad[k\lej][j-k\ 查看详情

ural-1901spaceelevators

题目：NowadaysspaceshipsareneverlaunchedfromtheEarth‘ssurface.ThereisahugespaceportplacedinthegeostationaryorbitandconnectedtotheEarthwithcarbonnanotubecables.Peopleandcargoaredeliveredtotheorbitbyelevat 查看详情

ural2089experiencedcoachtwosat

DescriptionMishatrainsseveralACMteamsattheuniversity.Heisanexperiencedcoach,andhedoesnotunderestimatethemeaningoffriendlyandcollaborativeatmosphereduringtrainingsessions.Itusedtobethatway,butoneofthet 查看详情

ural2020trafficjaminflowertown

2020.TrafficJaminFlowerTownTimelimit:1.0secondMemorylimit:64MBHavingreturnedfromSunCity,Dunnotoldallhisfriendsthateveryshortymayhaveapersonalautomobile.Immediatelyafterthatsomanycitizenstookafancyofbe 查看详情

luogup1855榨取kkksc03

题目描述以下皆为真实的故事。洛谷2的团队功能是其他任何oj和工具难以达到的。借助洛谷强大的服务器资源，任何学校都可以在洛谷上零成本的搭建oj并高效率的完成训练计划。为什么说是搭建oj呢？为什么高效呢？因为，你... 查看详情

p1855榨取kkksc03

题目描述洛谷2的团队功能是其他任何oj和工具难以达到的。借助洛谷强大的服务器资源，任何学校都可以在洛谷上零成本的搭建oj并高效率的完成训练计划。为什么说是搭建oj呢？为什么高效呢？因为，你可以上传私有题目，团... 查看详情

ural1424minibus

MinibusTimelimit:1.0secondMemorylimit:64MBBackgroundMinibusdriverSergeyA.Greedsonhasbecometotallyfamousforhisphenomenalgreediness.Heclaimedtimeandagainthatheheldhimselfinreadinesstothrottlehisbrothera 查看详情

ural2016magicandscience

2016.MagicandScienceTimelimit:1.0secondMemorylimit:64MBScientistswhospecializeinwitchcrafthaverecentlydiscoveredanewelementaryparticlecalledamagion.Studyingthelawsofmagions’movement,agroupofthre 查看详情

ural2021scarilyinteresting!

2021.Scarilyinteresting!Timelimit:1.0secondMemorylimit:64MBThisyearatMonstersUniversityitisdecidedtoarrangeScareGames.AttheGamesallcampusgathersatthestadiumstands,andtheScareprogramstudentsdivideintot 查看详情