相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4900
原版题面：http://oi.cyo.ng/wp-content/uploads/2017/05/ctsc2017_day1.pdf
解题报告
我们做一个前缀和，发现问题变为询问一个区间内大于某个数的数有多少个
区间我们可以用滑动窗口来维护
询问大于某个数有多少可以用$BIT$来维护
总的时间复杂度：$O(n \log n)$
因为本题数据很水，所以过$10^7$的数据很轻松
当然标算是$O(n)$的算法
但我忘掉怎么证正确性了 qwq
Code
#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;
const int N = 40000009;
int k,n,seed,s,sum[N];
int ans1, ans2, ans3, MX, INF;
bool p[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline int R() {
seed = ((seed * 12321) ^ 9999) & 32767;
return seed;
}
class Fenwick_Tree{
int arr[N],tot;
public:
inline void modify(int pos, int delta) {
tot += delta;
for (int i = pos + MX; i <= INF; i += lowbit(i)) {
arr[i] += delta;
}
}
inline int query(int pos) {
int ret = tot;
for (int i = pos + MX; i > 0; i -= lowbit(i)) {
ret -= arr[i];
}
return ret;
}
}B1,B2;
int main() {
#ifdef DBG
freopen("11input.in", "r", stdin);
#endif
k = read();
seed = read();
s = read();
n = k * 2 + 1;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
p[i] = (R() >> 7) & 1;
cnt += p[i];
}
int cur = 1;
while (cnt > k) {
while (!p[cur]) {
++cur;
}
p[cur] = 0;
--cnt;
}
while (cnt < k) {
while (p[cur]) {
++cur;
}
p[cur] = 1;
++cnt;
}
for (int i=1;i<=n;i++) {
p[i + n] = p[i];
}
for (int i = 1; i <= n * 2; ++i) {
sum[i] = sum[i - 1] + (p[i]? 1: -1);
MX = max(MX, abs(sum[i]));
}
INF = MX << 1;
for (int i = 1; i <= n; i++) {
if (p[i]) {
B1.modify(sum[i], 1);
} else {
B2.modify(-sum[i], 1);
}
}
for (int i = 1; i <= n; i++) {
if (!p[i]) {
int tmp = B1.query(sum[i]);
if (tmp == 0) {
ans1 = i;
} else if (tmp == s) {
ans2 = i;
}
B2.modify(-sum[i], -1);
if (B2.query(-sum[i]) == s) {
ans3 = i;
}
if (ans1 && ans2 && ans3) {
break;
}
} else {
B1.modify(sum[i], -1);
}
if (p[i + n]) {
B1.modify(sum[i + n], 1);
} else {
B2.modify(-sum[i + n], 1);
}
}
printf("%d\n%d\n%d", ans1, ans2, ans3);
return 0;
}
Excellent post. Keep writing such kind of info on your
site. Im really impressed by your blog.
Hello there, You’ve performed a fantastic job.
I’ll definitely digg it and for my part suggest
to my friends. I’m confident they’ll be benefited from
this web site.
Superb, what a webpage it is! This website gives useful information to
us, keep it up.
Good information. Lucky me I discovered your blog by accident (stumbleupon).
I’ve saved it for later!
Greetings! I’ve been following your weblog for a long time
now and finally got the courage to go ahead and give you a shout out from Kingwood Texas!
Just wanted to say keep up the fantastic work!
It’s actually a cool and helpful piece of information. I’m satisfied that you shared this
useful info with us. Please keep us up to date like this.
Thank you for sharing.
Everyone loves what you guys are up too. This sort of clever work and reporting!
Keep up the amazing works guys I’ve incorporated you guys to my own blogroll.
For most recent information you have to visit the web and on internet
I found this website as a most excellent
web site for newest updates.
Do you mind if I quote a few of your posts as long as I provide
credit and sources back to your blog? My blog site is in the
exact same area of interest as yours and my users would genuinely benefit from a lot of the information you present here.
Please let me know if this ok with you. Appreciate it!
Wonderful beat ! I would like to apprentice whilst you amend your site, how can i
subscribe for a blog site? The account aided me a applicable deal.
I have been a little bit familiar of this your broadcast offered vibrant clear idea
Nice response in return of this matter with firm arguments and explaining all
on the topic of that.
Wow, this article is good, my sister is analyzing these kinds of things,
therefore I am going to let know her.
I’ve been surfing online more than 3 hours nowadays, yet
I never discovered any interesting article like yours.
It’s pretty price sufficient for me. In my opinion, if
all site owners and bloggers made excellent content material as you probably did, the net shall be much more useful than ever before.
Aw, this was an extremely nice post. Taking the time and actual effort to make a top
notch article… but what can I say… I procrastinate a whole lot and don’t seem to get anything done.
Hello! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing several weeks of hard work due to no back up.
Do you have any methods to stop hackers?
This is really interesting, You are a very skilled blogger. I have joined your feed and look forward to seeking more of your great post. Also, I’ve shared your site in my social networks!
It’s amazing in support of me to have a web site, which is helpful in support of my
know-how. thanks admin
Hi there to all, how is all, I think every one is getting more from this website, and your views are nice in favor of
new viewers.
What’s up colleagues, how is all, and what you desire to say on the topic of this
article, in my view its genuinely remarkable in favor of
me.
bookmarked!!, I love your blog!
Hi everyone, it’s my first go to see at this website, and paragraph is truly
fruitful in support of me, keep up posting these types of content.
It’s a shame you don’t have a donate button! I’d
without a doubt donate to this outstanding blog! I guess for now
i’ll settle for bookmarking and adding your RSS feed to my
Google account. I look forward to brand new updates and will share this blog with my Facebook group.
Talk soon!
Hello my friend! I wish to say that this article is amazing, great written and include
approximately all important infos. I’d like to look more posts like this .
Your style is very unique in comparison to other folks I have read stuff from.
I appreciate you for posting when you’ve got the opportunity,
Guess I will just bookmark this page.
I’m impressed, I need to say. Really hardly ever do I encounter a weblog that’s both educative and entertaining, and let me tell you, you’ve got hit the nail on the head. Your thought is outstanding; the issue is something that not enough individuals are talking intelligently about. I’m very completely happy that I stumbled across this in my seek for one thing referring to this.