【AtCoder】[Regular Contest 068 E] Snuke Line

Qizy Fenwick Tree, 数据结构, 解题报告

相关链接

题目传送门：http://arc068.contest.atcoder.jp/tasks/arc068_c
数据生成器：http://paste.ubuntu.com/23948002/
官方题解：https://arc068.contest.atcoder.jp/editorial

解题报告

设一个间隔$d$,一种物品的覆盖区间长度为$L$
若 $L \ge d$ 则一定能取，否则只会被遍历到一次
于是我们就从小到达枚举$d$，同时维护$L$，把$L < d$的扔到$BIT$里就可以啦！
复杂度: $O(n{log^2}n)$，不过因为$BIT$的常数关系，所以跑得飞快

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000+9;

int n,m;
struct Event{
	int l,r,len;
	inline Event() {}
	inline Event(int _l, int _r) {l = _l; r = _r; len = r - l + 1;}
	inline bool operator < (const Event &B) const {return len < B.len;}
}e[N];

class Fenwick_Tree{
	int cnt[N];
	public:
		inline void modify(int l, int r) {
			for (int i=l-1;i;i-=lowbit(i)) cnt[i]--;
			for (int i=r;i;i-=lowbit(i)) cnt[i]++; 
		}
		inline int query(int p) {
			int ret = 0;
			for (int i=p;i<=m;i+=lowbit(i)) ret += cnt[i];
			return ret;
		}
	private:
		inline int lowbit(int x) {
			return x & -x;
		}
}BIT; 

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;
}

int main() {
	n = read(); m = read();
	for (int i=1,l,r;i<=n;i++) {
		l = read(); r = read();
		e[i] = Event(l, r);
	}
	sort(e+1, e+1+n);
	for (int d=1,p=1,sta=n;d<=m;d++) {
		for (;p<=n&&e[p].len==d-1;p++) {
			--sta;
			BIT.modify(e[p].l, e[p].r);
		}
		int vout = 0;
		for (int i=d;i<=m;i+=d) 
			vout += BIT.query(i);
		printf("%d\n",vout+sta);
	}
	return 0;
}

171 thoughts to “【AtCoder】[Regular Contest 068 E] Snuke Line”

  17. I loved as much as you will receive carried out right here.
    The sketch is attractive, your authored material stylish. nonetheless, you command
    get bought an nervousness over that you wish be delivering the following.
    unwell unquestionably come further formerly again since exactly the same nearly very often inside case you shield this
    hike.

    Reply

  23. Hi there, just became aware of your blog through Google, and
    found that it’s really informative. I am going to watch out for brussels.
    I will be grateful if you continue this
    in future. Lots of people will be benefited
    from your writing. Cheers!

    Reply

  30. This is very interesting, You’re a very skilled blogger.
    I’ve joined your rss feed and look forward to seeking more of your magnificent post.
    Also, I’ve shared your site in my social networks!

    Reply

  37. Helpful information. Fortunate me I found your site unintentionally, and I am surprised why this accident didn’t came about in advance!
    I bookmarked it.

    Reply

  42. Thanks for your marvelous posting! I actually enjoyed reading it,
    you’re a great author. I will always bookmark your blog and will come back
    from now on. I want to encourage continue your great writing, have a nice
    weekend!

    Reply

  43. Definitely believe that which you stated. Your favorite justification appeared to
    be on the web the easiest thing to be aware of. I say to you,
    I definitely get annoyed while people think about worries that they just don’t know about.
    You managed to hit the nail upon the top as well as defined out the whole thing without having side effect ,
    people could take a signal. Will probably be back to get more.
    Thanks

    Reply

  47. hello!,I like your writing so a lot! percentage we keep in touch
    extra about your article on AOL? I require an expert in this area
    to resolve my problem. May be that is you!
    Having a look forward to peer you.

    Reply

  49. Greetings! I know this is kinda off topic nevertheless
    I’d figured I’d ask. Would you be interested in trading
    links or maybe guest writing a blog post or vice-versa?

    My blog discusses a lot of the same subjects as yours and I
    believe we could greatly benefit from each other. If you’re interested feel free to
    send me an e-mail. I look forward to hearing from you!
    Fantastic blog by the way!

    Reply

  52. Hi there, I discovered your web site by the use of Google while searching for a comparable topic, your web site came up, it
    appears to be like good. I have bookmarked it in my google bookmarks.

    Hello there, simply become alert to your blog thru Google, and located that it
    is truly informative. I am gonna watch out
    for brussels. I’ll appreciate should you continue this in future.
    Many people will probably be benefited from your writing.
    Cheers!

    Reply

  56. Oh my goodness! Impressive article dude! Many thanks, However I am going through problems with your RSS.

    I don’t know why I cannot join it. Is there anybody else having the same RSS issues?
    Anyone who knows the solution will you kindly respond?
    Thanx!!

    Reply

  69. Excellent post. Keep writing such kind of info on your blog.

    Im really impressed by it.
    Hey there, You’ve performed a great job. I’ll certainly
    digg it and in my opinion recommend to my friends.

    I am confident they will be benefited from this website.

    Reply

  71. After looking over a handful of the blog posts on your website, I truly appreciate your technique of writing
    a blog. I saved as a favorite it to my bookmark website list and will be checking back soon. Please check
    out my website too and let me know how you feel.

    Reply

  83. Does your site have a contact page? I’m having trouble locating it but, I’d like to shoot
    you an e-mail. I’ve got some creative ideas for your blog you might
    be interested in hearing. Either way, great website and I look forward to seeing it improve over time.

    Reply

  94. Hi I am so delighted I found your weblog, I really found you by mistake,
    while I was searching on Askjeeve for something else, Anyways I am here now and would just like to say cheers for
    a remarkable post and a all round thrilling blog (I also love the theme/design), I don’t have time to read through it all at the minute
    but I have book-marked it and also added your RSS feeds, so when I have time I will be back to read a great deal more, Please do keep up
    the great b.

    Reply

  108. It’s remarkable to pay a visit this web page and reading the views of all mates regarding this post, while I am also keen of getting
    know-how.

    Reply

  133. I love your blog.. very nice colors & theme. Did you make this website yourself or did you hire someone to do it for you? Plz respond as I’m looking to create my own blog and would like to know where u got this from. appreciate it

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *