题目传送门: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; }
另外,这题如果强制在线的话,貌似可以上主席树?
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.
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!
I used to be able to find good info from your articles.
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.
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.
Spot on with this write-up, I actually think this
web site needs a great deal more attention. I’ll probably be back again to see more, thanks for the info!
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.
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.
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.
Hi, yup this post is really fastidious and I have learned lot of things from it concerning blogging.
thanks.
If some one wants expert view regarding blogging
then i suggest him/her to visit this webpage, Keep up the good work.
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..
WOW just what I was searching for. Came here by searching for
coconut oil
Would love to incessantly get updated great weblog! .
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?
Thanks for sharing your thoughts about match.com free trial.
Regards
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.
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.
Fantastic beat ! I would like to apprentice whilst you amend your web site, how could i subscribe for a blog website?
The account aided me a applicable deal. I were a
little bit acquainted of this your broadcast offered shiny clear concept
Heya i am for the primary time here. I came across this board and I to find It truly useful & it
helped me out much. I’m hoping to offer something back
and help others such as you aided me.
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
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!
I have read so many articles on the topic
of the blogger lovers except this article is actually a good paragraph, keep it up.
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
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.