题解：AT_abc389_c [ABC389C] Snake Queue

yyycj · 2025-01-18 21:54:04 · 题解

题目传送门

题目简述

有一个放蛇的队列，起初是空的。

现在有 Q 次操作，操作有三种类型：

• 类型 1：输入格式 1 l，将一条长度为 l 的是加入队列尾，它的头部坐标为前一条蛇的尾坐标，如果加入前队列里没有蛇，则头坐标为 0。设的尾坐标等于头坐标加长度。
• 类型 2：输入格式 2，删除队列最前面的蛇，后面的蛇的头坐标会因此改变。
• 类型 3：输入格式 3 k，输出第 k 条蛇的头坐标，保证出现此操作蛇的数量 \ge k。

主要思路

首先，如果操作 2 直接根据题意模拟，遍历整个队列，将每条蛇的头坐标改变，并删除第一条蛇，时间复杂度为 O(Q^{2})，对于 Q\le3\times 10^{5}，显然超时。

所以说我们可以不删除第一条蛇，而是定义一个 sum 变量，初值为 0，对于每个操作 2，将 sum 加上第一条蛇的长度，这样在进行操作 3 时，答案即为（记存储蛇头坐标的数组为 S，进行操作 2 的次数为 p）S_{k+p}-sum，表示由于删掉了 p 条蛇，但数组里存放的蛇的数量没有减少，所以要加上一个 p，并且操作 2 后蛇的头坐标会改变，但数组里也没有改变，所以减去 sum 就表示减去前面删掉的蛇的长度的总和。

最最后：十年 OI 一场空，___。

AC Code

#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
using namespace std;

#define OUT 0
#define endl '\n'
#define MAMBA return
typedef long long ll;
const int N = 3e5 + 10;
const int INF = 0x3f3f3f3f;
typedef unsigned long long ull;
int _pow(int a,int b){int x=1,y=a;while(b>0){if(b&1)x*=y;y*=y;b>>=1;}return x;}
void print(ll x){if(x<0){putchar('-');x=-x;}if(x>9){print(x/10);}putchar(char(x%10+'0'));}
void print(int x){if(x<0){putchar('-');x=-x;}if(x>9){print(x/10);}putchar(char(x%10+'0'));}
void print(string s){int n=s.length();for(int i=0;i<n;i++)putchar(s[i]);}
inline int read_int(){int f=1,x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline ll read_ll(){int f=1;ll x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
// ----------------------------

// ----------------------------
ll len[N];
ll head_idx[N];
// ----------------------------

int man() {
    int q = read_int();
    // ------------------------
    int op,k;
    ll sum = 0;
    int pop_cnt = 0;
    int snake_cnt = 0;
    while (q--) {
        op = read_int();
        if (op == 1) {
            len[++snake_cnt] = read_int();
            head_idx[snake_cnt] = head_idx[snake_cnt-1] + len[snake_cnt-1];
        }
        else if (op == 2) sum += len[++pop_cnt];
        else {
            k = read_int();
            print(head_idx[k+pop_cnt]-sum);
            putchar('\n');
        }
    }
    MAMBA OUT;
}
                                                                                                                                                                                                                                                                                                                                    int main() {MAMBA man();}