題目鏈接：點擊查看
題目大意：給出 n 條平行于 x 軸的線段，每條線段都的 [ l , r ] 都位于 [ 1 , X ] 之間，每條線段的高度為 d，也就是距離 x 軸的位置，接下來給出 m 次詢問，每次詢問給出一個 x 和 k ，問：在點 x 處向上的前 k 個線段的高度之和為多少，如果 k 大于點 x 處的線段總數(shù)，那么缺少的線段用最高的線段的高度補上
題目分析：因為題目要求了強制在線，所以不能用線段樹+離線來完成，區(qū)間 [ 1 , X ] 上的每個點可以通過掃描線的思想，將 n 條線段的屬性轉(zhuǎn)換為前綴和的思想，這樣每個點都可以獨立成為一個前綴和的版本了，所有的版本可以利用主席樹來維護，每個版本中維護當前所有線段高度的前綴和，這樣每次查詢時，只需要查詢第 x 個版本的主席樹，在內(nèi)部二分找到 k 的位置，然后返回前綴即可，對于 k 不足的地方，在 l == r 的地方稍微處理一下就可以了
代碼：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>v,node[N];
/*主席樹*/
struct Node
{int l,r,num;LL sum;
}tree[N*50];int cnt,root[N];void init()
{root[0]=0;tree[0].l=tree[0].r=tree[0].sum=tree[0].num=0;cnt=1;
}void update(int pos,int flag,int &k,int l,int r)
{tree[cnt++]=tree[k];k=cnt-1;tree[k].num+=flag;tree[k].sum+=flag*v[pos-1];if(l==r)return;int mid=l+r>>1;if(pos<=mid)update(pos,flag,tree[k].l,l,mid);elseupdate(pos,flag,tree[k].r,mid+1,r);
}LL query(int rt,int k,int l,int r)
{if(l==r)return 1LL*v[l-1]*k;int mid=l+r>>1;int num=tree[tree[rt].l].num;LL sum=tree[tree[rt].l].sum;if(num>=k)return query(tree[rt].l,k,l,mid);elsereturn sum+query(tree[rt].r,k-num,mid+1,r);
}
/*主席樹*/
/*離散化*/
void discreate()
{sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
}int get_id(int x)
{return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
/*離散化*/int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int n,m,X,P;while(scanf("%d%d%d%d",&n,&m,&X,&P)!=EOF){init(); for(int i=1;i<=X+1;i++)node[i].clear();for(int i=1;i<=n;i++){int l,r,d;scanf("%d%d%d",&l,&r,&d);node[l].push_back(d);node[r+1].push_back(-d);v.push_back(d);}discreate();for(int i=1;i<=X;i++){root[i]=root[i-1];for(auto t:node[i])update(get_id(abs(t)),t<0?-1:1,root[i],1,v.size());}LL pre=1;while(m--){int x,a,b,c;scanf("%d%d%d%d",&x,&a,&b,&c);int k=(pre*a+b)%c;LL ans=query(root[x],k,1,v.size());if(pre>P)ans*=2;printf("%lld\n",ans);pre=ans;}}return 0;
}
?
超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術(shù)人生
總結(jié)
以上是生活随笔 為你收集整理的HDU - 4866 Shooting(主席树+扫描线) 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔 推薦給好友。
