首页 > 其他分享 >P10550 [THUPC2024] 贸易 题解

P10550 [THUPC2024] 贸易 题解

时间:2024-06-03 17:55:24浏览次数:25  
标签:P10550 int 题解 fro back cin 括号 THUPC2024

正式场上拿了这题的首 \(A\),让队伍不至于无奖而返。

思路

容易发现题目的买入卖出过程形似一个括号匹配。

那么我们可以对每一种类型的物品做括号匹配。

若是一个匹配的括号在询问区间内则可以记入答案。

就变成了一个二维数点问题。

离线树状树组即可。

Code

#include <bits/stdc++.h>
using namespace std;

#define fro(i, x, y) for (int i = (x); i <= (y); i++)
#define pre(i, x, y) for (int i = (x); i >= (y); i--)

const int N = 5e5 + 10;

int n, q, a[N], c[N], p[N], t[N], l[N], r[N], ans[N];
vector<int> d[N];
vector<int> o[N];

inline void upd(int x) { while (x) t[x]++, x -= (x & (-x)); }
inline auto ask(int x) { int r = 0; while (x <= n) r += t[x], x += (x & (-x)); return r; }

signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  fro(i, 1, n) cin >> a[i];
  fro(i, 1, n) cin >> c[i];
  fro(i, 1, n) {
    if (a[i] == 0) d[c[i]].push_back(i);
    if (a[i] == 1) if (!d[c[i]].empty()) p[i] = d[c[i]].back(), d[c[i]].pop_back();
  }
  fro(i, 1, q) cin >> l[i] >> r[i], o[r[i]].push_back(i);
  fro(i, 1, n) {
    if (p[i]) upd(p[i]);
    for (auto j : o[i]) {
      ans[j] = ask(l[j]);
    }
  }
  fro(i, 1, q) cout << ans[i] << "\n";
  return 0;
}

标签:P10550,int,题解,fro,back,cin,括号,THUPC2024
From: https://www.cnblogs.com/JiaY19/p/18229364

相关文章

  • 关于vue关闭页面时去除定时器失效问题解决
    1.先去除页面缓存,这个在路由部分 2.    ......
  • 第十五届蓝桥杯国赛C++B组文字题解
    A:合法密码暴力跑一下即可,坑点是pdf有换行,字母不算字符,最后答案是:400。B:选数概率观察到第二个分数的分母很大,猜测\((a+b+c)\times(a+b+c-1)=20910‬\)发现无整数解,于是考虑到可能被约分了,将\(20910\times2=41820\)最后得到\(a+b+c=105\)然后就......
  • [SDOI2008] Sue 的小球 题解
    题目描述首先将彩蛋按照横坐标从小到大排序,依次标号为\(1\simn\)。显然,\(Sue\)走过一段时间后,走过的点一定属于一段连续区间。所以本题采用区间\(dp\)。不妨先做一个简单转化,由于每个彩蛋初始高度确定,若想让总分最高,就要使扣分最少。所以下面的\(dp\)从扣分最少入手。设......
  • DVWA靶场---csrf遇到的问题解决方法
    1.解决low等级不携带cookie访问诈骗网站:设置---隐私与安全---浏览器隐私---增强型跟踪保护---自定义---cookie---跨站跟踪型cookie。2.解决medium等级referer显示不完整解决方法:在服务器的html上加一段:<metaname="referrer"content="no-referrer-when-downgrade">当从......
  • 力扣2891每日一题题解
    题目:给你一个仅由小写英文字母组成的字符串 s 。如果一个字符串仅由单一字符组成,那么它被称为 特殊 字符串。例如,字符串 "abc" 不是特殊字符串,而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度,如果不存在出......
  • P7311 [COCI2018-2019#2] Maja题解
    [COCI2018-2019#2]Maja题目描述蜜蜂Maja在一个神奇的牧场里为花朵传粉。牧场可用一个\(N\timesM\)的矩阵表示。在第\(i\)行第\(j\)列有\(C_{i,j}\)朵未传粉的花。Maja从位于第\(A\)行第\(B\)列的蜂巢出发,并前往牧场的一些区域后返回。Maja可以在\(1\)步内......
  • rt-thread 系统pm组件在4.1.1版本的无法正常唤醒的问题解决方法
    在老的rt-thread版本系统pm组件调试ok,后来使用4.1.1版本时发现进入低功耗后无法正常唤醒,问题解决路径如下硬件信息:cpu STM32L431CCT6新建系统打开pm组件后也没有drv_pm.c和drv_lptim.c自动添加,需要到系统目下找到并复制到driver目录下C:\RT-ThreadStudio\repo\Extract\R......
  • [题解]UVA11235 Frequent values
    https://www.luogu.com.cn/problem/UVA11235没看到多测调了半天每组数据给定\(n,q\)。接下来给出一个长度为\(n\)的不降序列\(A\)。接下来\(q\)次询问,每次询问给定\(l,r\),求\(A_{l\simr}\)中出现最多的那个数出现了多少次。\(1\len,q\le10^5\)。序列不降,意味着一个数在序......
  • CF1228E Another Filling the Grid 题解
    tag:容斥原题+组合数设F[i]F[i]F[i]表示至少......
  • [leetcode 第 400 场周赛]题解
    第一题:classSolution{publicintminimumChairs(Strings){intx=0;intans=0;for(inti=0;i<s.length();i++){if(s.charAt(i)=='E'){x--;if(x<0){ans++;x=0;......