洛谷P7870题解

传送锚点

摸鱼环节

「Wdoi-4」兔已着陆

题目背景

铃瑚和清兰是从月之都到达幻想乡的两只月兔。正因为降落到了幻想乡进行调查，因此她们通过开团子屋制作团子出售的方式，在幻想乡生活。

为了应对越发繁荣的市场，她们向河城荷取购置了一台团子机器，可以高效地生产出五颜六色的团子。不同颜色的团子的售价不尽相同。由于每天顾客数量很多，购买的团子数量也不少，所以清兰总是搞不清楚一大堆团子的售价如何。

清兰找到了你，希望你能告诉她每次售出团子时，这些团子的总价格。

题目描述

清兰使用河童的机器可以生产出各种各样颜色的团子。她发现，对于颜色为 \(\bm c\) 的团子，它的售价为 \(\bm c\)。同时，团子机器有个特性，那就是生产出来的团子的颜色必然是一段连续的整数。

为了储存已经生产出来的团子，清兰使用了一种类似于「栈」的结构。在一天的开始，这个栈为空栈。现在有 \(n\) 次操作，分为两种：

1. \(\colorbox{f0f0f0}{\verb!1 l r!}\) ：团子机器生产出来了颜色为 \(l,l+1,\cdots r-1,r\) 的团子。清兰将这些团子依次入栈。也就是在栈顶依次加入 \(l,l+1,l+2,\cdots r-1,r\) 。
2. \(\colorbox{f0f0f0}{\verb!2 k!}\) ：有一位客人想要购买 \(k\) 个团子。此时清兰会依次从栈顶取出 \(k\) 个团子并售出。保证 \(k\) 不大于当前栈内的团子个数。

你要做的，就是对于每个操作 \(2\) 输出这些团子的总价格。

输入格式

第一行有一个整数 \(n\)，表示操作的个数。
接下来 \(n\) 行描述一组询问。第一个整数 \(op\) 表示询问的种类，若为 \(1\) 则为操作 \(1\)，为 \(2\) 则为操作 \(2\)。

• 对于操作 \(1\)，接下来有两个整数 \(l,r\)，含义如题面所示。
• 对于操作 \(2\)，接下来有一个整数 \(k\)，含义如题面所示。

输出格式

若干行。对于每次操作 \(2\)，输出这些团子的售价之和。

样例 #1

样例输入 #1

6
1 1 14
2 5
1 14 19
1 1 9
2 8
2 10

样例输出 #1

60
44
124

提示

样例 \(2\) 见下发的附件 \(\textbf{\textit{stack2.in}/\textit{stack2.out}}\)。

数据范围

• 对于前 \(30\%\) 的数据，\(n,l,r\le100\)。
• 对于另外 \(20\%\) 的数据，\(l=r\)。
• 对于另外 \(20\%\) 的数据，\(k\le 10\)。
• 对于 \(100\%\) 的数据，\(1\le n\le 5\times 10^5\)，\(0\le l\le r \le 10^6\)，\(1\le k \le 10^{12}\)。

窝又来水题解了最近比较懒，于是还是日更一篇8。这道题有效得训练了我们圈钱处理有序大数据的新方法。

正片开始

一眼数据范围，很明显不能直接暴力塞。但是呢，咱可以发现这些有序的团子可以用公式直接计算出，即\(ans=\frac{(l+r)(r-l+1)}{2}\)，so只需要维护个团子段的左右端点即可。

操作一，
code：

cin>>l>>r;
s[cnt++]=make_pair(l,r);

操作二，
code：

cnt--;
cin>>k;
while(k)
{
   if(s[cnt].second-s[cnt].first+1>k)
    {
        ans+=(s[cnt].second*2-k+1)*k/2;
        s[cnt].second-=k;//新右端点
        k=0;
    }
    else
    {
        ans+=(s[cnt].first+s[cnt].second)*(s[cnt].second-s[cnt].first+1)/2;
        k-=(s[cnt].second-s[cnt].first+1);
        cnt--;
    }
}
cout<<ans<<endl;
cnt++;

注意数据大小，需要开\(long\) \(long\)。

十年OI一场空，不开\(long\) \(long\)见祖宗。

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6+5,mod=1e9+7;
int n,cnt=1;
pair<ll,ll>s[N];
int main()
{
    cin>>n;
    {
        for(int i=1;i<=n;i++)
        {
            ll ans=0,k=0;
            int op,l,r;
            cin>>op;
            if(op==1)
            {
                cin>>l>>r;
                s[cnt++]=make_pair(l,r);
            }
            else
            {
                cnt--;
                cin>>k;
                while(k)
                {
                    if(s[cnt].second-s[cnt].first+1>k)
                    {
                        ans+=(s[cnt].second*2-k+1)*k/2;
                        s[cnt].second-=k;
                        k=0;
                    }
                    else
                    {
                        ans+=(s[cnt].first+s[cnt].second)*(s[cnt].second-s[cnt].first+1)/2;
                        k-=(s[cnt].second-s[cnt].first+1);
                        cnt--;
                    }
                }
                cout<<ans<<endl;
                cnt++;
            }
        }
    }
    return 0;
}

完结收工！！！！！

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)