首页 > 其他分享 >题解 数数

题解 数数

时间:2023-08-24 14:44:57浏览次数:45  
标签:node 数数 int 题解 询问 que 区间

题目链接

可持久化平衡树看上去很行的样子,但是我不会啊。。。

先来考虑一个简化版的问题:求区间 \([1,n]\) 中 \(\le H_i\) 的元素个数。

这显然是好做的,用权值树状数组就行。

回到本题,显然:询问区间 \([l,r]\) 中 \(\le H_i\) 的个数,等价与区间 \([1,r]\) 的答案减去区间 \([1,l-1]\) 的答案。所以,我们将一个询问拆成上述形式的两个询问,并且附上一个 \(k\),表示这个询问对答案是加还是减,如果是加,就赋值位 \(1\),减则赋值为 \(-1\)。即:

struct node {
    int r,id,k,h;
    //分别表示,右边界,第几个问题,加还是减,h的值
};

然后按照右边界排序,依次做权值树状数组即可。

由于 \(h,a\) 的范围很大,所以先要离散化。

完整代码:

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

const int N=2e5+10;
int T,n,q,m;
int a[N],b[N];
int ans[N];
int tr[N];
struct node {
    int k,r,h,id;
};
vector<node> que;

int cmp(node x,node y) {
    return x.r<y.r;
}

int find(int x) {
    return lower_bound(b+1,b+1+m,x)-b;
}

int lowbit(int x) {
    return x&(-x);
}

void modify(int nd,int x) {
    for(int i=nd;i<=m;i+=lowbit(i)) tr[i]+=x;
}

int query(int nd) {
    int ans=0;
    for(int i=nd;i;i-=lowbit(i)) ans+=tr[i];
    return ans;
}

void Solve() {
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        b[++m]=a[i];
    }
    for(int i=1;i<=q;i++) {
        int l,r,h; cin>>l>>r>>h;
        b[++m]=h;
        que.push_back({1,r,h,i});
        que.push_back({-1,l-1,h,i});
    }
    sort(b+1,b+1+m);
    m=unique(b+1,b+1+m)-b-1;
    sort(que.begin(),que.end(),cmp);
    int nd=0;
    for(auto t:que) {
        while(nd+1<=t.r) {modify(find(a[nd+1]),1); nd++;}
        ans[t.id]+=t.k*query(find(t.h));
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<' ';
    cout<<endl;
}

void Clear() {
    for(int i=1;i<=m;i++) b[i]=0;
    for(int i=1;i<=n;i++) a[i]=0;
    for(int i=1;i<=m;i++) tr[i]=0;
    for(int i=1;i<=q;i++) ans[i]=0;
    n=m=q=0;
    que.clear();
}

int main() {
    cin>>T;
    while(T--) {
        Solve();
        Clear();
    }
    return 0;
}

标签:node,数数,int,题解,询问,que,区间
From: https://www.cnblogs.com/zhangyuzhe/p/17654089.html

相关文章

  • 国标视频云服务EasyGBS国标视频平台迁移服务器后无法启动的问题解决方法
    国标视频云服务EasyGBS支持设备/平台通过国标GB28181协议注册接入,并能实现视频的实时监控直播、录像、检索与回看、语音对讲、云存储、告警、平台级联等功能。平台部署简单、可拓展性强,支持将接入的视频流进行全终端、全平台分发,分发的视频流包括RTSP、RTMP、FLV、HLS、WebRTC等格......
  • P3742题解
    思路只需要让z串做到和y串一样,就得让y串每个字母(题意如此)均小于x串。所以只要x串有一项小于y串,那么就输出-1,否则输出y串。下面是核心代码:#include<bits/stdc++.h>usingnamespacestd;intn;stringx,y;intmain(){ cin>>n>>x>>y; for(inti=0;i<n;i++) { if(x[i]......
  • 【问题解决】容器部署MySQL的数据在docker commit导出的镜像中丢失
    问题起因最近公司有个甲方项目参加竞赛,要求在(基于kubeflow/arena)平台上部置应用,可以将MySQL打包在应用一起,也可以分开部署,没有提供volume相关的支持。大意是可以把初始好的数据直接拿到平台上。经过本人在Linux虚机中启动MySQL容器导入数据再dockercommit出镜像部署到平台......
  • 「题解」Codeforces 825G Tree Queries
    点权转边权,把边权设为两个端点的\(\min\),然后发现询问\(x\)的答案,就是询问\(x\)与所有黑点的虚树,边权的\(\min\)是多少。假设要判定答案是否\(\geqk\),那么就是询问\(x\)只经过\(\geqk\)是否能到达所有黑点,于是想到建立Kruskal重构树,那么\(x\)与所有黑点的LCA......
  • 题解 P8816 [CSP-J 2022] 上升点列
    P8816[CSP-J2022]上升点列题目大意给定\(n\)个点,你可以任意添加\(k\)个点,从中选择若干点使得序列中任意相邻两点间的欧几里得距离恰好为\(1\)而且横坐标、纵坐标值均单调不减。换言之,求二维最长上升子序列。solution:很容易想到动态规划,根据最长上升子序列的套路,可以......
  • P1830题解
    思路:利用桶存储轰炸区域,双重循环。在存储轰炸区域时将次数刷新,也就是pos[j][k]=i;。下面是核心代码:for(inti=1;i<=x;i++){ intx1,x2,y1,y2; cin>>x1>>y1>>x2>>y2; for(intj=x1;j<=x2;j++) { for(intk=y1;k<=y2;k++) { vis[j][k]++; pos[j][k]=i; } }......
  • CF1820 & 1819 题解
    Div2A答案取决于_连续段长度,有一些细节,比如什么时候答案要加一减一,以及字符串是单独的^。Div2B首先先把全\(1\)串给特判掉。记将字符串视为首位相接的环的时,最大\(1\)连续段长度为\(x\),答案为\({\lfloor{x+1\over2}\rfloor}({\lfloor{x\over2}\rfloor+1})\)......
  • CF1681E Labyrinth Adventures 题解
    题意有一个\(n\timesn\)的方格图,坐标编号类似平面直角坐标系,左下角为\((1,1)\)。这个方格图被分成了\(n\)层,左下角\((1,1)\)为第一层,随后每层都向外拓展一圈,如下图就是\(n=5\)的时候的情况:层与层之间有墙隔开,但每层都有两个门,分别分布在该层顶部和右侧,门是双向的......
  • h5页面开发常见问题解决方案,助你快速排除问题
    h5页面作为目前广告、宣传以及用户交互的重要工具之一。但是在开发的过程中往往会遇到一些问题,比如兼容性、性能、布局等方面的常见问题。下面,广州名锐讯动将介绍一些h5页面开发常见问题并提供解决方案,帮助您快速排除问题。1.兼容性问题当我们在不同设备和浏览器操作时,h5页面可能......
  • 国标GB28181视频平台EasyGBS国标平台无法正常启动的问题解决方案
    EasyGBS国标视频云服务是基于国标GB/T28181协议的视频能力平台,可实现的视频功能包括:实时监控直播、录像、检索与回看、语音对讲、云存储、告警、平台级联等功能。平台部署简单、可拓展性强,支持将接入的视频流进行全终端、全平台分发,分发的视频流包括RTSP、RTMP、FLV、HLS、WebRTC......