数对(动态开点)

简介: 笔记

题目描述


给定一个长度为 n nn 的整数数列 和两个整数 x xx、y yy。

10.png

请你判断一共有多少个数对 ( l , r ) (l, r)(l,r) 同时满足以下条件:



输入描述


11.png

输出描述


输出一个整数,表示满足条件的数对的数量。


示例1#


输入:


5 3 3

4 6 5 3 7


输出:


5


说明:


满足要求的数对一共 5组,分别是 (1,1)、(2,2)、(3,3)、(4,4)、(3,4)


分析


12.png

代码

注意 i ii从1开始,那么s [ l − 1 ] s[l - 1]s[l−1]中即从0 00开始,所以事先需要插入 s [ 0 ] s[0]s[0]这个节点。


然后就是套动态开点线段树的模板了。


#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 500010;
struct node {
    int l, r;
    int v, add;
}tr[N << 6];
int n, x, y;
int a[N], ans, s[N];
int root, idx;
int L = -(1ll << 60), R = (1ll << 60);
void pushdown(int p, int l, int r) {
    if(tr[p].add) {
        int mid = l + r >> 1;
        tr[tr[p].l].add += tr[p].add, tr[tr[p].l].v += (mid - l + 1) * tr[p].add;
        tr[tr[p].r].add += tr[p].add, tr[tr[p].r].v += (r - mid) * tr[p].add;
        tr[p].add = 0;
    }
}
void pushup(int p) {
    tr[p].v = tr[tr[p].l].v + tr[tr[p].r].v;
}
void modify(int &p, int l, int r, int ql, int qr, int v) {
    if(!p) p = ++idx;
    if(l >= ql && r <= qr) { tr[p].add += v; tr[p].v += (r - l + 1) * v; return ; }
    pushdown(p, l, r);
    int mid = l + r >> 1;
    if(ql <= mid) modify(tr[p].l, l, mid, ql, qr, v);
    if(qr > mid) modify(tr[p].r, mid + 1, r, ql, qr, v);
    pushup(p);
    return ;
}
int query(int p, int l, int r, int ql, int qr) {
  if(!p) return 0;
    if(l >= ql && r <= qr) return tr[p].v;
    int mid = l + r >> 1;
    pushdown(p, l, r);
    int res = 0;
    if(ql <= mid) res += query(tr[p].l, l, mid, ql, qr);
    if(qr > mid) res += query(tr[p].r, mid + 1, r, ql, qr);
    return res;
}
signed main() {
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] -= y; s[i] = s[i - 1] + a[i]; }
    modify(root, L, R, s[0], s[0], 1);
    for (int i = 1; i <= n; i++) {
        ans += query(root, L, R, s[i] - x, R);
        modify(root, L, R, s[i], s[i], 1);
    }
    cout << ans << endl;
  return 0;
}
相关文章
|
uml
状态机
首先需要考虑涉及到哪些状态节点和哪些事件,如何方便状态节点的获取、状态节点如何串联起来呢?串联的方式下,如何拿到下一个状态节点?如果基于角色,如何实现? 我们知道工作流可以实现基于角色进行流程的流转,但是此时我们涉及到事件和状态,会出现多个分支,如果使用工作流实现,流程处理上,比如activiti上,可能比较复杂,因此考虑比较轻量级的状态机来实现的话,相对来说要方便一些。
1344 0
状态机
|
10月前
|
Java 应用服务中间件 Maven
如何将 Spring Boot 应用程序部署为 WAR?
如何将 Spring Boot 应用程序部署为 WAR?
513 1
|
10月前
|
负载均衡 算法
SLB-Backend的负载均衡算法
【10月更文挑战第19天】
135 5
|
11月前
|
监控 数据可视化 关系型数据库
开发者如何使用云数据库 SelectDB 版
【10月更文挑战第20天】开发者如何使用云数据库 SelectDB 版
180 0
electron 下网页获取 micphone 权限
electron 下网页获取 micphone 权限
|
7月前
|
Java 程序员 开发者
悲催,放到 Map 中的元素取不出来了
本文通过一个程序员小明遇到的实际问题,深入探讨了在使用 HashMap 时由于键对象的可变性导致的数据访问异常。
|
存储 算法 C++
【C++高阶(六)】哈希的应用--位图&布隆过滤器
【C++高阶(六)】哈希的应用--位图&布隆过滤器
|
Java 数据库连接 API
【测试开发】使用 Mybatis-Plus 的 BaseMapper 接口与 Service 接口
【测试开发】使用 Mybatis-Plus 的 BaseMapper 接口与 Service 接口
【测试开发】使用 Mybatis-Plus 的 BaseMapper 接口与 Service 接口
|
C++
【C++知识点】访问限定符
【C++知识点】访问限定符
196 0