題干：

小A有一個含有n個非負整數(shù)的數(shù)列與m個區(qū)間，每個區(qū)間可以表示為li,ri。

它想選擇其中k個區(qū)間， 使得這些區(qū)間的交的那些位置所對應的數(shù)的和最大。（是指k個區(qū)間共同的交，即每個區(qū)間都包含這一段，具體可以參照樣例）

?

在樣例中，5個位置對應的值分別為1,2,3,4,6，那么選擇[2,5]與[4,5]兩個區(qū)間的區(qū)間交為[4,5]，它的值的和為10。

?收起

輸入

第一行三個數(shù)n,k,m(1<=n<=100000,1<=k<=m<=100000)。 接下來一行n個數(shù)ai，表示小A的數(shù)列(0<=ai<=10^9)。 接下來m行，每行兩個數(shù)li,ri，表示每個區(qū)間(1<=li<=ri<=n)。

輸出

一行表示答案

輸入樣例

5 2 3 1 2 3 4 6 4 5 2 5 1 4

輸出樣例

10

解題報告：

? ?這題解法很多，因為元素值都是正數(shù)，所以我們可以枚舉每一個位置，找到區(qū)間最左端的滿足的，這一定就是對于當前i作為右端點的最大答案了。怎么看最左端滿足的呢？也就是找到左端k個值，也就是找到左端第k大就行了，但是這題要判斷一下是否一共這棵線段樹中有k個元素，我們用tree[1].sum就可以得到。

? 同樣，維護位置和值 也可以用set。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; vector<int> vv[MAX]; int n,m,k; ll a[MAX]; struct TREE {int l,r;int sum; } tree[MAX*4]; void pushup(int cur) {tree[cur].sum = tree[cur*2].sum + tree[cur*2+1].sum; } void build(int l,int r,int cur) {tree[cur].l = l;tree[cur].r = r;if(tree[cur].l == tree[cur].r) {tree[cur].sum = 0;return ;}int m = (l+r)>>1;build(l,m,cur*2);build(m+1,r,cur*2+1);pushup(cur); } int query(int tar,int cur) {if(tree[cur].l == tree[cur].r) return tree[cur].l;if(tar <= tree[cur*2].sum) return query(tar,cur*2);else return query(tar - tree[cur*2].sum,cur*2+1); } void update(int tar,int val,int cur) {if(tree[cur].l == tree[cur].r) {tree[cur].sum += val; return;}int m = tree[cur*2].r;if(tar <= m) update(tar,val,cur*2);else update(tar,val,cur*2+1); pushup(cur); } int main() {ll ans=0;cin>>n>>k>>m;build(1,n,1);for(int i = 1; i<=n; i++) scanf("%lld",a+i),a[i] += a[i-1];for(int x,y,i = 1; i<=m; i++) {scanf("%d%d",&x,&y);vv[x].pb(x);vv[y+1].pb(-x);}for(int i = 1; i<=n; i++) {int up = vv[i].size();for(int j = 0; j<up; j++) {if(vv[i][j] > 0) update(vv[i][j],1,1);else update(-vv[i][j],-1,1);} if(tree[1].sum >= k) {int pos = query(k,1);ans = max(ans,a[i] - a[pos-1]);} }printf("%lld\n",ans);return 0; }

首先排序右端點從小到大，然后枚舉右端點（保證所枚舉的那個端點最少有k個區(qū)間可以覆蓋）作為所求的交區(qū)間的右端點，這時候需要求出交區(qū)間的左端點，我們可以知道，右端點確定下，如果左端點越靠左，這個區(qū)間的范圍約大。為了保證所交區(qū)間有k個，我們需要找到第k小的左端點，為了保證我枚舉的右端點肯定是交區(qū)間的右端點，我們必須邊枚舉，邊單點更新左端點。
?

#include<bits/stdc++.h> #define inf 1e18 #define ll long long #define N 300010 #define lson rt<<1 #define rson rt<<1|1 #define mo 1000000007 using namespace std; typedef pair<int,int> P; inline ll read() {ll x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; } int n,m,K; ll sz[N*4],ans,sum[N]; struct node {int l,r; } s[N]; bool cmp(node a,node b) {if (a.r==b.r) return a.l>b.l;return a.r<b.r; } void pushup(int rt) {sz[rt]=sz[lson]+sz[rson]; } void modify(int rt,int l,int r,int pos) {if (l==r) {sz[rt]++;return ;}int mid=(l+r)>>1;if (pos<=mid) modify(lson,l,mid,pos);else modify(rson,mid+1,r,pos);pushup(rt); } int query(int rt,int l,int r,int x) {if (l==r) return l;int mid=(l+r)>>1;if (x<=sz[lson]) return query(lson,l,mid,x);else return query(rson,mid+1,r,x-sz[lson]); } int main() {n=read(),K=read(),m=read();for (int i=1; i<=n; i++) {sum[i]=read();sum[i]+=sum[i-1];}for (int i=1; i<=m; i++) s[i].l=read(),s[i].r=read();sort(s+1,s+m+1,cmp);for (int i=m-K+2; i<=m; i++) modify(1,1,n,s[i].l);for (int i=m-K+1; i>=1; i--) {modify(1,1,n,s[i].l);int x=query(1,1,n,K);if (x<=s[i].r) ans=max(ans,sum[s[i].r]-sum[x-1]);}printf("%lld",ans);return 0; }

枚舉i作為左端點的。

#include<bits/stdc++.h> #define ll long long using namespace std; const int MAX = 100005; ll sum[MAX] ; ll a[MAX]; multiset<int> ss; vector<int> vv[MAX];int main() {int n,k,m;while(~scanf("%d%d%d",&n,&k,&m) ) {memset(sum,0,sizeof sum);ss.clear();for(int i = 1; i<=n; i++) vv[i].clear();for(int i = 1; i<=n; i++) scanf("%lld",&a[i]),sum[i] = sum[i-1] + a[i];while(m--) {int l,r;scanf("%d%d",&l,&r);vv[l].push_back(r);}ll ans = 0;for(int i = 1; i<=n; i++) {int up = vv[i].size();for(int j = 0 ; j<up ; j++) ss.insert(vv[i][j]);if(ss.empty() == 0) {while(ss.size() > k || *ss.begin() < i) {ss.erase(ss.begin());if(ss.size() == 0) break;} }if(ss.size() == k) ans = max(ans , sum[*(ss.begin())] - sum[i-1]);}printf("%lld\n" , ans);}return 0; }

?

?

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define fi first #define se second #define pb(x) push_back(x) using namespace std; typedef long long ll; typedef pair<ll ,int> pii; const ll N = 101000, siz = 20, mod = 1e9+7, blk = 316, eps = 1e-10; ll fpow(ll a, ll b){ll ret=1;for(a%=mod;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod;return ret;} priority_queue<int, vector<ll >, greater<int> >q; ll n, m, k, sum[N], ans, t; pair<ll ,ll >a[N]; int main(){cin>>n>>k>>m;for(ll i=1;i<=n;i++){cin>>t;sum[i] = sum[i-1]+t;}for(ll i=0;i<m;i++)cin>>a[i].fi>>a[i].se;sort(a, a+m);for(ll i=0;i<m;i++){q.push(a[i].se);while(!q.empty() && q.top() < a[i].fi)q.pop();while(q.size() > k) q.pop();if(q.size() == k){//cout<<a[i].fi<<" "<<q.top()<<endl;ans = max(ans, sum[q.top()]-sum[a[i].fi-1]);}}cout<<ans<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 5700】【51nod - 1672】 区间交（贪心，STLset 或线段树第k大）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。