HDU 4325 离散化+树状数组 或者 不使用树状数组

题意：给出一些花的开放时间段，然后询问某个时间点有几朵花正在开放。

由于ti<1e9，我们需要先将时间离散化，然后将时间点抽象为一个数组中的点，显然，我们需要进行区间更新和单点查询，可以考虑线段树与树状数组两种做法，一般的，树状数组是用来维护区间和与单点修改的，那么，如何通过树状数组进行区间更新和单点查询呢，联想到差分数组，差分数组可以在o(1)的时间内进行区间的更新，但是单点查询的效率为o(n)，显然不能用于处理此题，这时，考虑树状数组维护差分数组，就可以o(logn)地进行区间更新（更新差分数组的 l, r+1即可，使sub[l]++,sub[r+1]--），o(logn)地查询单点值(求差分数组前缀和)//树状数组维护差分数

#include<bits/stdc++.h#define N 100005#define mod 998244353 using namespace std; typedef long long ll; int sub[N<<1],n,l[N],r[N],tim[N],nn; int lowbit(int x){ return x&-x;}; int add(int x,int val) {while(x<=nn){sub[x]+=val;x+=lowbit(x);} } int query(int x) {int ans=0;while (x>0){ans+=sub[x];x-=lowbit(x);}return ans; } int main() {int t;cin>>t;for(int ca=1;ca<=t;ca++){memset(sub,0, sizeof(sub));vector<int>mp;int q,L,R;cin>>n>>q;for(int i=1;i<=n;i++){scanf("%d%d",l+i,r+i);mp.push_back(l[i]);mp.push_back(r[i]);}for(int i=1;i<=q;i++){scanf("%d",tim+i);mp.push_back(tim[i]);}nn=mp.size();sort(mp.begin(),mp.end());unique(mp.begin(),mp.end());for(int i=1;i<=n;i++){L=lower_bound(mp.begin(),mp.end(),l[i])-mp.begin()+1;R=lower_bound(mp.begin(),mp.end(),r[i])-mp.begin()+1;add(L,1);add(R+1,-1);}//for(int i=1;i<=mp.size();i++)cerr<<query(i)<<endl;printf("Case #%d:\n",ca);for(int i=1;i<=q;i++){int pos=lower_bound(mp.begin(),mp.end(),tim[i])-mp.begin()+1;printf("%d\n",query(pos));}}return 0; }

 

嘤嘤嘤~~博客写完，我就后悔了，本题的区间更新和单点查询操作是分开的，那么我为什么搞这么麻烦还用树状数组，直接差分数组求和后不就能o(1)单点查询了吗。。但是总体复杂度不变，仍为o(nlogn)
（n为离散化后，映射中点的个数，），常数降低了很多，，虽然运行时间只是由312ms到296ms，但是写起来简单了许多，以下是没有使用树状数组的ac代码

//树状数组维护差分数组 #include<bits/stdc++.h> #define N 100005 #define mod 998244353 using namespace std; typedef long long ll; int sub[N<<1],n,l[N],r[N],tim[N],nn; int main() {int t;cin>>t;for(int ca=1;ca<=t;ca++){memset(sub,0, sizeof(sub));vector<int>mp;int q,L,R;cin>>n>>q;for(int i=1;i<=n;i++){scanf("%d%d",l+i,r+i);mp.push_back(l[i]);mp.push_back(r[i]);}for(int i=1;i<=q;i++){scanf("%d",tim+i);mp.push_back(tim[i]);}nn=mp.size();sort(mp.begin(),mp.end());unique(mp.begin(),mp.end());for(int i=1;i<=n;i++){L=lower_bound(mp.begin(),mp.end(),l[i])-mp.begin()+1;R=lower_bound(mp.begin(),mp.end(),r[i])-mp.begin()+1;sub[L]++;sub[R+1]--;}for(int i=1;i<=nn;i++)sub[i]+=sub[i-1];printf("Case #%d:\n",ca);for(int i=1;i<=q;i++){int pos=lower_bound(mp.begin(),mp.end(),tim[i])-mp.begin()+1;printf("%d\n",sub[pos]);}}return 0; }

事实证明，只要多思考，问题就会更简单。算是一点小小的启发吧

转载于:https://www.cnblogs.com/xusirui/p/9427708.html

总结

以上是生活随笔为你收集整理的HDU 4325 离散化+树状数组 或者 不使用树状数组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。