sharepoint网站开发,西安关键词seo公司,聚名网抢注,网页设计与制作教程知识点牛客练习赛73 D 离别 思路: 对于每一个固定的右端点i#xff0c;我们都找到一个区间#xff08;l,r#xff09;使得区间中的点为左端点时 里面最大的的种数为k。 这个可以用队列或者vector来维护。
然后我们对于q个查询#xff0c;安装r从小到大排序。 开始遍历#xff0…牛客练习赛73 D 离别 思路: 对于每一个固定的右端点i我们都找到一个区间l,r使得区间中的点为左端点时 里面最大的的种数为k。 这个可以用队列或者vector来维护。
然后我们对于q个查询安装r从小到大排序。 开始遍历把now点更新到q.r点每次更新l【now】-r【now】这个区间的数都加1使得 从1到r 点 做为右端点的lr区间 全部更新然后我们查询q.l,q.r中的区间和是多少 就是答案了。 因为当 右端点 iq.l 的时候他更新的lr 区间必然是小于q.l的那剩下的右端的i 全部都是在(q.l,q.r)中,既查询q.l,q.r就是答案。
#include cstdio
#include cstring
#include string
#include cmath
#include iostream
#include algorithm
#include queue
#include cstdlib
#include stack
#include vector
#include set
#include map
#include bitset
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll,ll pii;
const ll mod20000311;
const ll N 3e510;
const double eps 1e-5;
//const double piacos(-1);
ll qk(ll a,ll b){ll ans1;while(b){if(b1) ansans*a%mod;aa*a%mod;b1;}return ans;
}struct p{int l,r;ll sum,lazy;
}s[N*4];
struct node{int l,r,id;bool operator(const node M) const{return rM.r;}
}a[N];
ll n,q,k;
queueint p[N];
ll ans[N];
ll ls[N],rs[N];
ll b[N];
void up(int rt){s[rt].sums[lson].sums[rson].sum;
}
void down(int rt){if(s[rt].lazy){s[lson].sum(s[lson].r-s[lson].l1)*s[rt].lazy;s[rson].sum(s[rson].r-s[rson].l1)*s[rt].lazy;s[lson].lazys[rt].lazy;s[rson].lazys[rt].lazy;s[rt].lazy0;}return;
}
void build(int rt,int l,int r)
{s[rt].ll,s[rt].rr;s[rt].sum0;s[rt].lazy0;if(lr) return;int mid(lr)1;build(lson,l,mid);build(rson,mid1,r);
}
void add(int rt,int L,int R,int v){if(s[rt].lLs[rt].rR){s[rt].sum(s[rt].r-s[rt].l1)*v;s[rt].lazyv;return;}down(rt);int mid(s[rt].ls[rt].r)1;if(midL) add(lson,L,R,v);if(midR) add(rson,L,R,v);up(rt);
}
ll q1(int rt,int L,int R){if(s[rt].lLs[rt].rR){return s[rt].sum;}down(rt);int mid(s[rt].ls[rt].r)1;ll ans0;if(midL) ansq1(lson,L,R);if(midR) ansq1(rson,L,R);up(rt);return ans;
}
void sovle(){cinnqk;for(int i1;in;i) cinb[i];int nowl1,nowr0;for(int i1;in;i){p[b[i]].push(i);if(p[b[i]].size()k) {int tp[b[i]].front();p[b[i]].pop();nowlmax(t1,nowl);}if(p[b[i]].size()k) {nowrmax(nowr,p[b[i]].front());}ls[i]nowl,rs[i]nowr;// coutls[i] rs[i]endl;}for(int i1;iq;i) {cina[i].la[i].r;a[i].idi;}build(1,1,n);sort(a1,a1q);int now0;for(int i1;iq;i){while(nowa[i].r) {now;if(ls[now]rs[now]) add(1,ls[now],rs[now],1);//coutq1(1,1,1)endl;}ans[a[i].id]q1(1,a[i].l,a[i].r);}//coutq1(1,1,1)endl;for(int i1;iq;i) coutans[i]endl;
}
int main()
{iosint t1;//cint;while(t--) sovle();return 0;
}
