Train Car Selection的秘密武器：掌握SWF和Flash中心的核心技巧

题目链接

题面

题目大意

给出列车初始节数以及操作次数，对于每一次操作查询车厢价值最小的节数及价值。每节车厢的初始价值均为0。
对于每次查询，第一个数字位‘1’时，在火车头加‘ b’节车厢；第一个数字为‘2’时，在火车尾加‘b’节车厢；第一个数字为’3‘时，将所有的车厢的价值重新计算，在原价值基础上加b+(ind-1)*s。

题目分析

当在车头加车厢的时候，第一节车厢无论后面如何重新计算价值，它都是最小的。
当在车尾加车厢的时候 ，如果当前第一节车厢价值不为0，则新加的第一个车厢的下标及价值为答案。此时需要处理一下现有的数据。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{ll val,ind;}num[300010];
int main()
{
    ll n;int m;
    scanf("%I64d%d",&n,&m);
    int be=0,en=0,add=0;
    ll len=n;
    ll b=0,c=0;
    num[en].ind=1;
    num[en].val=0;
    while(m--){
        int a;
        scanf("%d",&a);
        if(a==1){
            int b1;
            scanf("%d",&b1);
            len+=b1;
            en=0;
            num[0].ind=1;
            num[0].val=-(num[en].ind-1)*c-b;
            printf("1 0\n");
        }
        else if(a==2){
            int b1;
            scanf("%d",&b1);
            if(num[en].val+(num[en].ind-1)*c+b!=0){
                num[++en].ind=len+1;
                num[en].val=-(num[en].ind-1)*c-b;
            }
            len+=b1;
            if(num[be].val+b==0){
                printf("1 0\n");
            }
            else{
                printf("%d 0\n",num[en].ind);
            }
            while(en>=2&&((num[en].val+(num[en].ind-1)*c-num[en-1].val-(num[en-1].ind-1)*c)*1.0/(num[en].ind-num[en-1].ind)<=(num[en-1].val+(num[en-1].ind-1)*c-num[en-2].val-(num[en-2].ind-1)*c)*1.0/(num[en-1].ind-num[en-2].ind))){
                num[en-1].ind=num[en].ind;
                num[en-1].val=num[en].val;
                en--;
            }
        }
        else{
            ll b1,c1;
            scanf("%I64d%I64d",&b1,&c1);
            b+=b1;
            c+=c1;
            while(en>=1&&(num[en-1].val+(num[en-1].ind-1)*c-num[en].val-(num[en].ind-1)*c<=0)){
                en--;
            }
            //cout<<en<<endl;
            printf("%I64d %I64d\n",num[en].ind,num[en].val+(num[en].ind-1)*c+b);
        }
    }
    return 0;
}