潍坊知名网站建设价格低,wordpress 菜单 导航,十大电子商务平台,广州交通站场建设管理中心网站题干#xff1a;
小A有一个含有n个非负整数的数列与m个区间#xff0c;每个区间可以表示为li,ri。
它想选择其中k个区间#xff0c; 使得这些区间的交的那些位置所对应的数的和最大。#xff08;是指k个区间共同的交#xff0c;即每个区间都包含这一段#xff0c;具体可…题干
小A有一个含有n个非负整数的数列与m个区间每个区间可以表示为li,ri。
它想选择其中k个区间 使得这些区间的交的那些位置所对应的数的和最大。是指k个区间共同的交即每个区间都包含这一段具体可以参照样例 在样例中5个位置对应的值分别为1,2,3,4,6那么选择[2,5]与[4,5]两个区间的区间交为[4,5]它的值的和为10。 收起
输入
第一行三个数n,k,m(1n100000,1km100000)。
接下来一行n个数ai表示小A的数列(0ai10^9)。
接下来m行每行两个数li,ri表示每个区间(1lirin)。
输出
一行表示答案
输入样例
5 2 3
1 2 3 4 6
4 5
2 5
1 4
输出样例
10
解题报告 这题解法很多因为元素值都是正数所以我们可以枚举每一个位置找到区间最左端的满足的这一定就是对于当前i作为右端点的最大答案了。怎么看最左端满足的呢也就是找到左端k个值也就是找到左端第k大就行了但是这题要判断一下是否一共这棵线段树中有k个元素我们用tree[1].sum就可以得到。 同样维护位置和值 也可以用set。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
vectorint 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*21].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 (lr)1;build(l,m,cur*2);build(m1,r,cur*21);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*21);
}
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*21); pushup(cur);
}
int main()
{ll ans0;cinnkm;build(1,n,1);for(int i 1; in; i) scanf(%lld,ai),a[i] a[i-1];for(int x,y,i 1; im; i) {scanf(%d%d,x,y);vv[x].pb(x);vv[y1].pb(-x);}for(int i 1; in; i) {int up vv[i].size();for(int j 0; jup; 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小的左端点为了保证我枚举的右端点肯定是交区间的右端点我们必须边枚举边单点更新左端点。
#includebits/stdc.h
#define inf 1e18
#define ll long long
#define N 300010
#define lson rt1
#define rson rt1|1
#define mo 1000000007
using namespace std;
typedef pairint,int P;
inline ll read() {ll x0,f1;char chgetchar();while (ch0||ch9) {if (ch-) f-1;chgetchar();}while (ch0ch9) xx*10ch-0,chgetchar();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.rb.r) return a.lb.l;return a.rb.r;
}
void pushup(int rt) {sz[rt]sz[lson]sz[rson];
}
void modify(int rt,int l,int r,int pos) {if (lr) {sz[rt];return ;}int mid(lr)1;if (posmid) modify(lson,l,mid,pos);else modify(rson,mid1,r,pos);pushup(rt);
}
int query(int rt,int l,int r,int x) {if (lr) return l;int mid(lr)1;if (xsz[lson]) return query(lson,l,mid,x);else return query(rson,mid1,r,x-sz[lson]);
}
int main() {nread(),Kread(),mread();for (int i1; in; i) {sum[i]read();sum[i]sum[i-1];}for (int i1; im; i) s[i].lread(),s[i].rread();sort(s1,sm1,cmp);for (int im-K2; im; i) modify(1,1,n,s[i].l);for (int im-K1; i1; i--) {modify(1,1,n,s[i].l);int xquery(1,1,n,K);if (xs[i].r) ansmax(ans,sum[s[i].r]-sum[x-1]);}printf(%lld,ans);return 0;
}
枚举i作为左端点的。
#includebits/stdc.h
#define ll long long
using namespace std;
const int MAX 100005;
ll sum[MAX] ;
ll a[MAX];
multisetint ss;
vectorint 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; in; i) vv[i].clear();for(int i 1; in; 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; in; i) {int up vv[i].size();for(int j 0 ; jup ; 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;
} #includebits/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 pairll ,int pii;
const ll N 101000, siz 20, mod 1e97, blk 316, eps 1e-10;
ll fpow(ll a, ll b){ll ret1;for(a%mod;b;b1,aa*a%mod)if(b1)retret*a%mod;return ret;}
priority_queueint, vectorll , greaterint q;
ll n, m, k, sum[N], ans, t;
pairll ,ll a[N];
int main(){cinnkm;for(ll i1;in;i){cint;sum[i] sum[i-1]t;}for(ll i0;im;i)cina[i].fia[i].se;sort(a, am);for(ll i0;im;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){//couta[i].fi q.top()endl;ans max(ans, sum[q.top()]-sum[a[i].fi-1]);}}coutansendl;return 0;
}
