#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
using ll = long long;
int n, p = 0;
int a[N], st[N], f[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        for (; p && a[st[p - 1]] < a[i]; --p)
        {
            f[st[p - 1]] = i;
        }
        st[p++] = i;
    }
    for (int i = 1; i <= n; i++)
        cout << f[i] << ' ';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, k, a[N];
deque<int> maxq, minq;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    // 区间最小
    for (int i = 0; i < k; i++)
    {
        while (!minq.empty() && minq.front() <= i - k)
            minq.pop_front();
        while (!minq.empty() && a[minq.back()] >= a[i])
            minq.pop_back();
        minq.push_back(i);
    }
    cout << a[minq.front()];
    for (int i = k; i < n; i++)
    {
        while (!minq.empty() && minq.front() <= i - k)
            minq.pop_front();
        while (!minq.empty() && a[minq.back()] >= a[i])
            minq.pop_back();
        minq.push_back(i);
        cout << ' ' << a[minq.front()];
    }
    cout << endl;

    // 区间最大
    for (int i = 0; i < k; i++)
    {
        while (!maxq.empty() && maxq.front() <= i - k)
            maxq.pop_front();
        while (!maxq.empty() && a[maxq.back()] <= a[i])
            maxq.pop_back();
        maxq.push_back(i);
    }
    cout << a[maxq.front()];
    for (int i = k; i < n; i++)
    {
        while (!maxq.empty() && maxq.front() <= i - k)
            maxq.pop_front();
        while (!maxq.empty() && a[maxq.back()] <= a[i])
            maxq.pop_back();
        maxq.push_back(i);
        cout << ' ' << a[maxq.front()];
    }
    cout << endl;
    return 0;
}

#include <bits\stdc++.h>
using namespace std;
char board[5];
bool dfs()
{
    if (strcmp(board, "XXXX") == 0)
    {
        return false;
    }
    for (int i = 0; i < 4; i++)
    {
        if (board[i] == 'O')
        {
            board[i] = 'X';
            if (!dfs())
            {
                board[i] = 'O';
                return true;
            }
            if (board[i + 1] == 'O')
            {
                board[i + 1] = 'X';
                if (!dfs())
                {
                    board[i] = 'O';
                    board[i + 1] = 'O';
                    return true;
                }
                board[i + 1] = 'O';
            }
            board[i] = 'O';
        }
    }
}
int main()
{
    char con[][5] = {"XOOO", "XXOO", "OXOO", "OXXO"};
    for (int i = 0; i < 4; i++)
    {
        strcpy(board, con[i]);
        if (!dfs())//you fail
            putchar('V');
        else
            putchar('L');
    }
    return 0;
}

#include<bits/stdc++.h>
using ll=unsigned long long;
const int N=(2e5)+5;
using namespace std;
int n;
int a[N];
ll sum=0;
ll ans=0;
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=n-1;i>=0;i--){
        ans+=a[i]*sum;
        sum+=a[i];
    }
    printf("%lld",ans);
    return 0;
}

#include<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
int n,m,x;
unordered_map<int,int> mp;//数值，对应位置
int f[N];//对于查询[l,r]，f[r]表示[l,r]要有相配答案，l的最右
int main() {
    scanf("%d%d%d",&n,&m,&x);
    int a;
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        f[i]=max(f[i-1],mp[a^x]);//找到达到要求的最左边界
        mp[a]=i;
    }
    int l,r;
    while(m--){
        scanf("%d%d",&l,&r);
        if(l<=f[r])
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

#include<bits/stdc++.h>
using ll=unsigned long long;
const int p=998244353;//取模
using namespace std;
int n;
ll x,y,f;
ll quick_pow(ll a){
    ll res=1;
    ll b=p-2;
    while(b){
        if(b&1){
            res=res*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        f=((f+1)*y%p)*quick_pow(y-x)%p;
    }
    cout<<f<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
const int N=(1e5)+5;
int n,x;//宽度和小青蛙需要去学校的天数。
ll sum[N];//石头总数前缀和
int main() {
    scanf("%d%d",&n,&x);
    x<<=1;//实际上让青蛙2x次过岸
    int h;//石头高度
    for(int i=1;i<n;i++)
    {
        scanf("%d",&h);
        sum[i]=sum[i-1]+h;//[l,r]区间的石头总高度为sum[r]-sum[l-1]
    }
    int y=1;//跳跃能力
    sum[n]=INT_MAX;//到对岸相当于有无数的石头
    for(int i=0;i<n-y;i++)
        while(sum[i+y]-sum[i]<x)//[i+1,i+y]区间不够2x只青蛙落脚
            y++;
    printf("%d",y);
    return 0;
}

```

---

# [蓝桥杯 2022 省 A] 扫描游戏

## 题目描述

有一根围绕原点 $O$ 顺时针旋转的棒 $OA$，初始时指向正上方（Y 轴正向）。平面中有若干物件，第 $i$ 个物件的坐标为 $\left(x_{i}, y_{i}\right)$，价值为 $z_{i}$。当棒扫到某个物件时，棒的长度会瞬间增长 $z_{i}$，且物件瞬间消失（棒的顶端恰好碰到物件也视为扫到)，如果此时增长完的棒又额外碰到了其他物件，也按上述方式消去（它和上述那个点视为同时消失）。

如果将物件按照消失的时间排序，则每个物件有一个排名，同时消失的物件排名相同，请输出每个物件的排名，如果物件永远不会消失则输出 $-1$。

## 输入格式

输入第一行包含两个整数 $n$、$L$，用一个空格分隔，分别表示物件数量和棒的初始长度。

接下来 $n$ 行每行包含第三个整数 $x_{i}, y_{i}, z_{i}$。

注意存在 $(x_{i}, y_{i})=(0,0)$ 的情况，这些点视为一开始就立刻被碰到。

## 输出格式

输出一行包含 $n$ 整数，相邻两个整数间用一个空格分隔，依次表示每个物件的排名。

## 样例 #1

### 样例输入 #1

#include<bits/stdc++.h>
using ll=long long;
const int N=4000;
using namespace std;
int n;
int not_prime[N+4];
vector<int> primes;
inline void init_primes(){
    for(int i=2;i<=N;i++){
        if(!not_prime[i]){
            primes.push_back(i);
        }
        for(int j:primes){
            if(i*j>N)
                break;
            not_prime[i*j]=true;
            if(i%j==0)
                break;
        }
    }
}
inline bool check(ll x){
    ll y=pow(x,0.5);
    if(y*y==x)
        return true;
    y=pow(x,1.0/3);
    if(y*y*y==x||(y+1)*(y+1)*(y+1)==x)//?
        return true;
    return false;
}
int main() {
    init_primes();
    int t;
    ll n;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&n);
        if(check(n)){
            printf("yes\n");
            continue;
        }
        bool flag=true;
        for(int i:primes){
            int cnt=0;
            while(n%i==0){
                n/=i;
                cnt++;
            }
            if(cnt==1){
                flag=false;
                break;
            }
        }
        if(flag&&check(n)){
            printf("yes\n");
        }
        else{
            printf("no\n");
        }

    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
vector<int> pa;
vector<ll> sum;

int find(int x) {
    if (x != pa[x]) {
        int root = find(pa[x]);
        sum[x] += sum[pa[x]];
        pa[x] = root;
    }
    return pa[x];
}

int main() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);

    pa.resize(n + 1);
    sum.resize(n + 1, 0);
    iota(pa.begin(), pa.end(), 0);
    int l, r;
    ll s;
    while (m--) {
        scanf("%d%d%lld", &l, &r, &s);
        int root_l = find(l - 1);
        int root_r = find(r);
        if (root_l != root_r) {
            pa[root_r] = root_l;
            sum[root_r] = s + sum[l - 1] - sum[r];
        }
    }
    while (q--) {
        scanf("%d%d", &l, &r);
        if (find(l - 1) == find(r)) {
            printf("%lld\n", sum[r] - sum[l - 1]);
        } else {
            printf("UNKNOWN\n");
        }
    }
    return 0;
}

long long ans1,ans2;//4430091，8335366
// 11~99999999
void solve1(){
    int cnt[40][5]={0};//和为几（1~36），几位数（1~4）
    for(int i=1;i<=9999;i++){
        int w=0,s=0,a=i;
        while(a){
            w++;
            s+=a%10;
            a/=10;
        }
        cnt[s][w]++;
    }
    for(int i=1;i<=36;i++){
        for(int j=1;j<=4;j++){
            int s=0;
            for(int k=1;k<=j;k++){
                s+=cnt[i][k];
            }
            ans1+=cnt[i][j]*s;
        }
    }
}
//答对，答错或者结束比赛
//300题拿了7分，答对1题加10分，答错分数归零。其中分数不可能>=100
void dfs(int t,int s){//题号，分数
    if(s==100)//到达100分时小蓝会直接停止答题
        return;
    if(s==70){
        ans2++;}
    if(t==31)//比赛结束
        return;
    dfs(t+1,s+10);//答对+1
    dfs(t+1,0);//答错分数归0
}
void solve2(){
    dfs(1,0);
}