题干：
小A有一个含有n个非负整数的数列与m个区间，每个区间可以表示为li,ri。
它想选择其中k个区间， 使得这些区间的交的那些位置所对应的数的和最大。（是指k个区间共同的交，即每个区间都包含这一段，具体可以参照样例）
在样例中，5个位置对应的值分别为1,2,3,4,6，那么选择[2,5]与[4,5]两个区间的区间交为[4,5]，它的值的和为10。
收起
输入
第一行三个数n,k,m(1<=n<=100000,1<=k<=m<=100000)。
接下来一行n个数ai，表示小A的数列(0<=ai<=10^9)。
接下来m行，每行两个数li,ri，表示每个区间(1<=li<=ri<=n)。 输出
一行表示答案 输入样例
5 2 3
1 2 3 4 6
4 5
2 5
1 4 输出样例
10 解题报告：
这题解法很多，因为元素值都是正数，所以我们可以枚举每一个位置，找到区间最左端的满足的，这一定就是对于当前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个区间可以覆盖）作为所求的交区间的右端点，这时候需要求出交区间的左端点，我们可以知道，右端点确定下，如果左端点越靠左，这个区间的范围约大。为了保证所交区间有k个，我们需要找到第k小的左端点，为了保证我枚举的右端点肯定是交区间的右端点，我们必须边枚举，边单点更新左端点。
#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;
}
京公网安备 11010502036488号