生活随笔
收集整理的这篇文章主要介绍了
牛客练习赛73 D 离别（线段树+右端点排序离线查询）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
牛客练习赛73 D 离别
思路: 对于每一个固定的右端点i，我们都找到一个区间（l,r）使得区间中的点为左端点时 里面最大的的种数为k。 这个可以用队列或者vector来维护。
然后我们对于q个查询，安装r从小到大排序。
开始遍历，把now点更新到q.r点，每次更新l【now】-r【now】这个区间的数都加1，使得 从1到r 点 做为右端点的（l，r）区间 全部更新，然后我们查询（q.l,q.r）中的区间和是多少 就是答案了。 因为当 右端点 i<q.l 的时候，他更新的（l，r） 区间必然是小于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 rt<<1
#define rson rt<<1|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 i=0;(i)<(n);i++)
#define rep1(i,n) for(int i=1;(i)<=(n);i++)
#define se secondusing namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef pair
<ll
,ll
> pii
;
const ll mod
=20000311;
const ll N
=3e5+10;
const double eps
= 1e-5;
ll
qk(ll a
,ll b
){ll ans
=1;while(b
){if(b
&1) ans
=ans
*a
%mod
;a
=a
*a
%mod
;b
>>=1;}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 r
<M
.r
;}
}a
[N
];
ll n
,q
,k
;
queue
<int> p
[N
];
ll ans
[N
];
ll ls
[N
],rs
[N
];
ll b
[N
];
void up(int rt
){s
[rt
].sum
=s
[lson
].sum
+s
[rson
].sum
;
}
void down(int rt
){if(s
[rt
].lazy
){s
[lson
].sum
+=(s
[lson
].r
-s
[lson
].l
+1)*s
[rt
].lazy
;s
[rson
].sum
+=(s
[rson
].r
-s
[rson
].l
+1)*s
[rt
].lazy
;s
[lson
].lazy
+=s
[rt
].lazy
;s
[rson
].lazy
+=s
[rt
].lazy
;s
[rt
].lazy
=0;}return;
}
void build(int rt
,int l
,int r
)
{s
[rt
].l
=l
,s
[rt
].r
=r
;s
[rt
].sum
=0;s
[rt
].lazy
=0;if(l
==r
) return;int mid
=(l
+r
)>>1;build(lson
,l
,mid
);build(rson
,mid
+1,r
);
}
void add(int rt
,int L
,int R
,int v
){if(s
[rt
].l
>=L
&&s
[rt
].r
<=R
){s
[rt
].sum
+=(s
[rt
].r
-s
[rt
].l
+1)*v
;s
[rt
].lazy
+=v
;return;}down(rt
);int mid
=(s
[rt
].l
+s
[rt
].r
)>>1;if(mid
>=L
) add(lson
,L
,R
,v
);if(mid
<R
) add(rson
,L
,R
,v
);up(rt
);
}
ll
q1(int rt
,int L
,int R
){if(s
[rt
].l
>=L
&&s
[rt
].r
<=R
){return s
[rt
].sum
;}down(rt
);int mid
=(s
[rt
].l
+s
[rt
].r
)>>1;ll ans
=0;if(mid
>=L
) ans
+=q1(lson
,L
,R
);if(mid
<R
) ans
+=q1(rson
,L
,R
);up(rt
);return ans
;
}
void sovle(){cin
>>n
>>q
>>k
;for(int i
=1;i
<=n
;i
++) cin
>>b
[i
];int nowl
=1,nowr
=0;for(int i
=1;i
<=n
;i
++){p
[b
[i
]].push(i
);if(p
[b
[i
]].size()>k
) {int t
=p
[b
[i
]].front();p
[b
[i
]].pop();nowl
=max(t
+1,nowl
);}if(p
[b
[i
]].size()==k
) {nowr
=max(nowr
,p
[b
[i
]].front());}ls
[i
]=nowl
,rs
[i
]=nowr
;}for(int i
=1;i
<=q
;i
++) {cin
>>a
[i
].l
>>a
[i
].r
;a
[i
].id
=i
;}build(1,1,n
);sort(a
+1,a
+1+q
);int now
=0;for(int i
=1;i
<=q
;i
++){while(now
<a
[i
].r
) {now
++;if(ls
[now
]<=rs
[now
]) add(1,ls
[now
],rs
[now
],1);}ans
[a
[i
].id
]=q1(1,a
[i
].l
,a
[i
].r
);}for(int i
=1;i
<=q
;i
++) cout
<<ans
[i
]<<endl
;
}
int main()
{ios
int t
=1;while(t
--) sovle();return 0;
}
总结
以上是生活随笔为你收集整理的牛客练习赛73 D 离别（线段树+右端点排序离线查询）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
