【BZOJ 1176】[Balkan2007] Mokia

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1176

这货二维BIT上不了
于是上CDQ

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int M = 200000+9;

struct OPT{
	int x,y,id,delta;
	inline OPT() {}
	inline OPT(int X, int Y, int ID, int DEL):x(X),y(Y),id(ID),delta(DEL){}
	inline bool operator < (const OPT &B) const {return x < B.x;}
}opt[M],buf[M];
int n,m,query_cnt,vout[M],hash[M*2],cnt;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	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;
}

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int sum[M*2];
	
	inline void modify(int w, int v){
		for (int i=w;i<=cnt;i+=lowbit(i)) sum[i] += v;
	}
	
	inline int query(int w){
		int ret = 0;
		for (int i=w;i;i-=lowbit(i)) ret += sum[i];
		return ret;
	}
};

void solve(int l, int r) {
	if (l >= r) return;
	int mid = l + r + 1 >> 1;
	solve(l,mid-1);	
	solve(mid,r);
	
	int p1 = l, p2 = mid;
	for (;p2<=r;p2++) {
		for (;p1 < mid && opt[p1].x <= opt[p2].x;p1++)
			if (!opt[p1].id) BIT::modify(opt[p1].y,opt[p1].delta);
		if (opt[p2].id) vout[opt[p2].id] += BIT::query(opt[p2].y)*opt[p2].delta;
	}
	
	for (int i=l;i<p1;i++) if (!opt[i].id) BIT::modify(opt[i].y,-opt[i].delta);
	merge(opt+l,opt+mid,opt+mid,opt+r+1,buf+1);
	memcpy(opt+l,buf+1,sizeof(opt[0])*(r-l+1));
}

int main(){
	read(); n = read();
	for (int t=read(),x1,y1,x2,y2;t!=3;t=read()) {
		if (t == 1) {
			opt[++m].x = read();
			opt[m].y = hash[++cnt] = read(); 
			opt[m].delta = read();
		} else {
			x1 = read(); y1 = hash[++cnt] = read(); hash[++cnt] = y1 - 1;
			x2 = read(); y2 = hash[++cnt] = read(); hash[++cnt] = y2 - 1;
			opt[++m].x = x1-1; opt[m].y = y1-1; opt[m].delta = 1;  opt[m].id = ++query_cnt;
			opt[++m].x = x2;   opt[m].y = y2;   opt[m].delta = 1;  opt[m].id = query_cnt;
			opt[++m].x = x1-1; opt[m].y = y2;   opt[m].delta = -1; opt[m].id = query_cnt;
			opt[++m].x = x2;   opt[m].y = y1-1; opt[m].delta = -1; opt[m].id = query_cnt;
		}
	}
	sort(hash+1,hash+1+cnt);
	cnt = unique(hash+1,hash+1+cnt) - hash - 1;
	for (int i=1;i<=m;i++) opt[i].y = lower_bound(hash+1,hash+1+cnt,opt[i].y) - hash;
	solve(1,m);
	for (int i=1;i<=query_cnt;i++) printf("%d\n",vout[i]);
	return 0;
}

另外,这题如果强制在线的话,貌似可以上主席树?

25 thoughts to “【BZOJ 1176】[Balkan2007] Mokia”

  1. We’re a group of volunteers and starting a new scheme in our community.
    Your site provided us with valuable information to work on. You’ve done a formidable job and our whole community will be thankful
    to you.

  2. Have you ever considered about including a little
    bit more than just your articles? I mean, what you say is
    valuable and all. However think of if you added some great visuals or video clips
    to give your posts more, “pop”! Your content is excellent but
    with images and clips, this website could definitely be one of the very
    best in its field. Amazing blog!

  3. Have you ever thought about creating an ebook or guest authoring
    on other websites? I have a blog centered on the
    same subjects you discuss and would really like to have you share some
    stories/information. I know my audience would value your work.
    If you’re even remotely interested, feel free to send me an e mail.

  4. Pretty section of content. I just stumbled upon your web site and in accession capital to assert that I acquire in fact
    enjoyed account your blog posts. Anyway I’ll be subscribing
    to your feeds and even I achievement you access consistently rapidly.

  5. We are a group of volunteers and opening
    a new scheme in our community. Your site offered us with valuable info to work on. You have done an impressive job and our whole community will be thankful to you.

  6. I have been exploring for a little bit for any high quality articles or weblog posts
    in this sort of space . Exploring in Yahoo I ultimately
    stumbled upon this site. Reading this info So i am glad to show that I’ve a
    very excellent uncanny feeling I found out just what I needed.
    I so much indubitably will make certain to don?t overlook this
    web site and provides it a look on a constant basis.

  7. May I just say what a comfort to uncover somebody that really knows what
    they’re discussing on the net. You certainly realize how to
    bring a problem to light and make it important. More people have to check this
    out and understand this side of the story. I was surprised you’re not
    more popular since you certainly have the gift.

  8. I am extremely impressed with your writing skills as well
    as with the format in your blog. Is this a paid subject or
    did you customize it yourself? Either way keep up the excellent quality writing, it is rare to peer a nice blog like this one nowadays..

  9. fantastic points altogether, you simply won a emblem new reader.

    What could you suggest about your publish that you simply made a few days
    in the past? Any sure?

  10. You could definitely see your enthusiasm within the work you
    write. The world hopes for more passionate writers like you who aren’t afraid to say
    how they believe. Always follow your heart.

  11. hey there and thank you for your information – I’ve definitely picked up something
    new from right here. I did however expertise
    a few technical points using this website, as I experienced to reload the
    website a lot of times previous to I could get it to load properly.
    I had been wondering if your web host is OK? Not that I’m complaining, but slow loading instances
    times will often affect your placement in google and can damage your high quality score if advertising and marketing with Adwords.
    Anyway I am adding this RSS to my e-mail and could look
    out for much more of your respective intriguing content.
    Ensure that you update this again very soon.

  12. I don’t know if it’s just me or if perhaps everybody else encountering issues with
    your website. It appears like some of the written text on your content are running off the screen. Can someone
    else please provide feedback and let me know if this is happening to
    them too? This might be a issue with my
    web browser because I’ve had this happen previously.
    Many thanks

  13. Everything is very open with a very clear explanation of the
    issues. It was truly informative. Your website is very helpful.
    Many thanks for sharing!

  14. I know this if off topic but I’m looking into starting my
    own weblog and was wondering what all is required to
    get set up? I’m assuming having a blog like yours would cost a pretty penny?
    I’m not very internet smart so I’m not 100% sure.
    Any suggestions or advice would be greatly appreciated.
    Kudos

  15. Have you ever considered creating an e-book or guest authoring on other blogs? I have a blog based on the same topics you discuss and would really like to have you share some stories/information. I know my viewers would value your work. If you are even remotely interested, feel free to send me an e mail.

Leave a Reply

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