代码源每日一题 div1 #603 丹钓战

题目链接丹钓战

人傻了，又是这种题看不出来怎么处理，前面刚写过一个类似的问题“Z”型矩阵，题解链接, 同样为二维数点问题，再写一篇题解吧。

可以看出来，对于每个从1~i的区间我们很好求，直接模拟即可。但是这些询问要求我们处理$[l,r]$之间的询问，这如何处理？

稍微观察一下有一个重大的性质，然而我死活观察不出来。先从1~i开始处理，对于询问$[l,r]$区间中的数对$(a_i,b_i)$，只要他在栈中的上一个数对的下标$<l$,那么这个数对必然是成功的。这个上一个就是指弹出不合法元素后的上一个。

假设模拟之后，每对$(a_i,b_i)$上一个下标为$j$,我们相当于统计每个区间，有多少数对$j<l$。所以这就是一个熟悉的二维数点模型。比较好的处理方法是离线+树状数组(dls说的）

处理步骤：

• 先模拟一遍，把所有$j$都求出来，特别的，栈为空时j=0
• 把所有的询问离线，区间按照左端点排序。
• 把所有的j按照从大到小排序。

对于每个询问，我们需要先插入那些$j<l$的下标，然后再统计即可

代码

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long LL;
const int N = 5e5 + 10;const LL INF = 1e17;
bool muti = false;
typedef pair<int,int> PII;int n, m;
int a[N], b[N];
int stk[N], top;
int ans[N];
PII lst[N];
struct Query
{
    int l, r, id;bool operator<(const Query& q) const {
    return l < q.l;}
}q[N];struct Fenwick {
    int c[N], n;inline void Init(int _n) {
    n = _n;for (int i = 1; i <= n; ++ i) c[i] = 0;}inline void Add(int x, int v) {
    for (; x <= n; x += x & -x) c[x] += v;}inline int Ask(int x) {
    int sm = 0;while(x) {
    sm += c[x];x &= x - 1;}return sm;}inline int Sum(int l, int r) {
    return Ask(r) - Ask(l - 1);}
} bit;
void solve() {
    scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= n; i++) scanf("%d", &b[i]);//哨兵top = 0;a[0] = 1e9, b[0] = 1e9;stk[++top] = 0;for(int i = 1; i <= n; i++) {
    while(a[stk[top]] == a[i] || b[stk[top]] <= b[i]) top--;lst[i] = {
    stk[top], i};stk[++top] = i;}sort(lst + 1, lst + 1 + n);bit.Init(n);for(int i = 0; i < m; i++) {
    int l, r;scanf("%d%d", &l, &r);q[i] = {
    l, r, i};}sort(q, q + m);for(int i = 0, j = 1; i < m; i++) {
    auto[l, r, id] = q[i];while(j <= n && lst[j].x < l) {
    bit.Add(lst[j].y, 1);j++;}ans[id] = bit.Sum(l, r);}for(int i = 0; i < m; i++) printf("%d\n", ans[i]);}
int main()
{
    
#ifdef ONLINE_JUDGE
#else freopen("A.txt", "r", stdin);
#endif// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T = 1;if(muti) cin >> T;while (T--) solve();return 0;
}