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

题目链接丹钓战

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

可以看出来，对于每个从1~i的区间我们很好求，直接模拟即可。

但是这些询问要求我们处理 [ l , r ] [l,r] [l,r]之间的询问，这如何处理？

稍微观察一下有一个重大的性质，然而我死活观察不出来。

先从1~i开始处理，对于询问 [ l , r ] [l,r] [l,r]区间中的数对 ( a i , b i ) (a_i,b_i) (ai​,bi​)，只要他在栈中的上一个数对的下标 < l <l,那么这个数对必然是成功的。

这个上一个就是指d出不合法元素后的上一个。

假设模拟之后，每对 ( a i , b i ) (a_i,b_i) (ai​,bi​)上一个下标为 j j j,我们相当于统计每个区间，有多少数对 j < l j < l j<l。

所以这就是一个熟悉的二维数点模型。

比较好的处理方法是离线+树状数组(dls说的）

处理步骤：

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

  
  

• 把所有的j按照从大到小排序。
  

  
  

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

代码

#include
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;
}