【NOI五连测】[D2T2] 取名字

题目传送门:http://pan.baidu.com/s/1hsLh92W
OJ传送门:http://oi.cdshishi.net:8080/Problem/1713

这一道题目,考试的时候,想了一个小时,完全没有思路,最后搞了30分的暴力QAQ
考试的时候一直在想如何将更改操作应用于硬币上
然而std是用硬币去操作中查询
为什么考试的时候没有想到呢?考试的时候是想到这样反向来搞的,但因为精神不好+懒所以没有深入思考
所以该睡的觉还是要睡的,该开的黑还是要开的

来说一说std的做法:
设一个硬币,比较大的值为mx,较小的值为mn。操作的阈值为v
则操作可以分为3类
1.mn < v
2.mn <= v < mx
3.mx <= v
对于第一类,明显不影响
对于第二类,明显是不管之前状态如何,全部变为mx
对于第三类,就是直接反转
所以我们可以找到最后一个第二类操作,然后查找之后有多少个三类操作即可

至于代码实现方面,我后来写的是BIT+线段树
std是二维线段树
我的要快一点,std空间要少很多,所以还是把std贴出来吧(std建树的时候有一点奇技淫巧)
std:http://paste.ubuntu.com/19496714/
my code:

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;

const int MAXN = 100000+9;

int n,m,arr[MAXN],rev[MAXN],val[MAXN],hash[MAXN*3],tot,MX;
vector<int> G[MAXN]; LL vout;

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
} 

namespace Chair_Tree{
	#define CT Chair_Tree
	#define lowbit(x) ((x)&-(x))
	#define N 10000000
	int cnt,ch[N][2],sum[N],ans_tmp;
	int q1[MAXN],q2[MAXN],root[MAXN*3];
	
	void modify(int &w, int l, int r, int val, int del){
		if (!w) w = ++cnt; sum[w] += del; 
		if (l < r) {
			int mid = (l + r + 1) / 2;
			if (val < mid) modify(ch[w][0],l,mid-1,val,del);
			else modify(ch[w][1],mid,r,val,del);
		}
	}
	
	inline void modify(int pos, int val, int del){
		for (int i=val;i<=tot;i+=lowbit(i)) 
			modify(root[i],1,m,pos,del);
	}
	
	void query(int w, int l, int r, int lim, int rim){
		if (lim <= l && r <= rim) ans_tmp += sum[w];
		else {
			int mid = (l + r + 1) / 2;
			if (lim < mid) query(ch[w][0],l,mid-1,lim,rim); if (rim >= mid) query(ch[w][1],mid,r,lim,rim); 
		}
	}
	
	inline int query(int pos, int l, int r){
		ans_tmp = 0; 
		for (int i=pos;i;i-=lowbit(i)) 
			query(root[i],1,m,l,r);
		return ans_tmp;
	}
	
	inline int GetMX(int L, int R) {
		int t1=0,t2=0,l=1,r=m,mid,tmp=0;
		for (int i=R;i;i-=lowbit(i)) q1[++t1] = root[i];
		for (int i=L;i;i-=lowbit(i)) q2[++t2] = root[i];
		for (int i=1;i<=t1;i++) tmp += sum[q1[i]];
		for (int i=1;i<=t2;i++) tmp -= sum[q2[i]];
		if (!tmp) return 0;
		else while (l < r) {
			mid = (l + r + 1) / 2; tmp = 0;
			for (int i=1;i<=t1;i++) tmp += sum[ch[q1[i]][1]];
			for (int i=1;i<=t2;i++) tmp -= sum[ch[q2[i]][1]]; if (tmp > 0) {
				l = mid;
				for (int i=1;i<=t1;i++) q1[i] = ch[q1[i]][1];
				for (int i=1;i<=t2;i++) q2[i] = ch[q2[i]][1];
			} else {
				r = mid - 1;
				for (int i=1;i<=t1;i++) q1[i] = ch[q1[i]][0];
				for (int i=1;i<=t2;i++) q2[i] = ch[q2[i]][0];
			}
		} return l;
	}
};

inline int find(int w){
	int l=1,r=tot,mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (hash[mid] < w) l = mid+1; else if (hash[mid] > w) r = mid-1;
		else return mid;;
	}
}

int main(){
	freopen("name.in","r",stdin);
	freopen("name.out","w",stdout); 
	n = read();
	for (int i=1;i<=n;i++) arr[i] = hash[++tot] = read();
	for (int i=1;i<=n;i++) rev[i] = hash[++tot] = read();
	m = read();
	for (int i=1,a,b,c;i<=m;i++) 
		a = read(), b = read(), val[i] = hash[++tot] = read(),
		G[a].push_back(i), G[b+1].push_back(-i);
	sort(hash+1,hash+1+tot);
	tot = unique(hash+1,hash+tot+1)-hash-1;
	for (int i=1;i<=n;i++) arr[i] = find(arr[i]);
	for (int i=1;i<=n;i++) rev[i] = find(rev[i]);
	for (int i=1;i<=m;i++) val[i] = find(val[i]);
	
	for (int k=1;k<=n;k++) {
		for (int i=0;i<(int)G[k].size();i++) { if (G[k][i] > 0) CT::modify(G[k][i],val[G[k][i]],1);
			else CT::modify(-G[k][i],val[-G[k][i]],-1);
		}
		int l=1,r=m,ans=0,mn=min(arr[k],rev[k]),mx=max(arr[k],rev[k]);
		ans = CT::GetMX(mn-1,mx-1);
		if (ans) {
			int tmp = CT::query(tot,ans,m) - CT::query(mx-1,ans,m);
			if (tmp % 2) vout += (LL)hash[mn];
			else vout += (LL)hash[mx];
		} else {
			int tmp = CT::query(tot,0,m) - CT::query(mx-1,0,m);
			if (tmp % 2) vout += (LL)hash[rev[k]];
			else vout += (LL)hash[arr[k]];
		}
	}
	printf("%lld\n",vout);
	return 0;
}	
 

23 thoughts to “【NOI五连测】[D2T2] 取名字”

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

  2. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored material stylish.
    nonetheless, you command get got an impatience over that you
    wish be delivering the following. unwell unquestionably come more formerly again as exactly the same nearly very often inside case you shield this increase.

  3. Hey there! Someone in my Myspace group shared this website with us
    so I came to give it a look. I’m definitely loving
    the information. I’m bookmarking and will be tweeting this to my followers!
    Excellent blog and terrific design and style.

  4. Thanks for your marvelous posting! I actually enjoyed reading it, you’re a great author.I will make certain to bookmark your blog and will often come back in the future.
    I want to encourage you continue your great writing, have a nice holiday
    weekend!

  5. My partner and I absolutely love your blog and find many of your post’s to be precisely what
    I’m looking for. Would you offer guest writers to write content for you personally?
    I wouldn’t mind producing a post or elaborating on some of
    the subjects you write in relation to here. Again, awesome web log!

  6. When I initially commented I clicked the “Notify me when new comments are added”
    checkbox and now each time a comment is added I get three emails with the same comment.
    Is there any way you can remove people from that service?
    Cheers!

  7. I savor, lead to I discovered exactly what I used to be taking a look for.
    You’ve ended my 4 day lengthy hunt! God Bless you man. Have a
    great day. Bye

  8. I was curious if you ever considered changing
    the page layout of your site? Its very well written; I
    love what youve got to say. But maybe you could a
    little more in the way of content so people
    could connect with it better. Youve got an awful lot
    of text for only having 1 or 2 images. Maybe
    you could space it out better?

  9. Great blog here! Also your site loads up very fast!

    What web host are you using? Can I get your
    affiliate link to your host? I wish my website loaded up as fast as yours lol

  10. Someone necessarily assist to make severely articles I’d state.
    That is the first time I frequented your web
    page and thus far? I surprised with the analysis you made to
    create this actual put up extraordinary. Wonderful task!

  11. I’m not sure exactly why but this weblog is loading incredibly slow for me.
    Is anyone else having this issue or is it a issue on my end?
    I’ll check back later and see if the problem still exists.

Leave a Reply

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