【HDU 1754】I Hate It

题目传送门:http://acm.split.hdu.edu.cn/showproblem.php?pid=1754
中文题面:http://blog.csdn.net/scnu_jiechao/article/details/8574166

其实我是来水BIT的

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 200000+9;
const int INF = 1000000000;

int n,m;
char pat[10];

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 MX[N],arr[N];
	
	inline void init(){
		for (int i=1;i<=n;i++)
			MX[i] = -INF;
	}
	
	inline void modify(int pos, int val){
		int pre = arr[pos]; arr[pos] = val;
		if (val >= pre) {
			for (int i=pos;i<=n;i+=lowbit(i)) 
				MX[i] = max(MX[i],val);
		} else {
			for (int i=pos;i<=n;i+=lowbit(i)) {
				MX[i] = arr[i];
				for (int j=lowbit(i)/2;j;j>>=1) 
					MX[i] = max(MX[i],MX[i-j]);
			}
		}
	}
	
	inline int query(int l, int r) {
		int ret = -INF;
		while (r >= l) {
			if (r-lowbit(r)+1 >= l) ret = max(ret, MX[r]), r -= lowbit(r);
			else ret = max(ret, arr[r]), r--;
		}
		return ret;
	}
};

int main(){
	while (~scanf("%d%d",&n,&m)) {
		BIT::init();
		for (int i=1;i<=n;i++) BIT::modify(i,read());	
		for (int i=1,l,r;i<=m;i++) {
			scanf("%s",pat+1);
			if (pat[1] == 'Q') l = read(), r = read(), printf("%d\n",BIT::query(l,r));
			else l = read(), r = read(), BIT::modify(l, r); 
		}
	}
	return 0;
}

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

【NOI六连测】[D1T1] 比赛

题目传送门:http://pan.baidu.com/s/1kVjNeeV
离线版题目:http://paste.ubuntu.com/18236489/
数据传送门:http://pan.baidu.com/s/1kUR6kTL

哎呀,绍兴一中的NOIP模拟题,第一眼拿到都一脸懵逼QAQ
想了一会儿发现,不就是总方案数减掉一个三位偏序吗?这个我会!
于是开开心心写完BIT+动态建点的线段树。然后小数据对拍,欸!居然没错 (~ ̄▽ ̄)→))* ̄▽ ̄*)o
然后一跑大数据,哎呀,空间简直炸的飞起! 然后再接下来的一个半小时里一直想办法压空间。
什么unsign short配合char之类的都用上了,然而还是不行QAQ,再加上时间复杂度也不一定过得去,于是弃疗

测完程序,发现CDQ+归并就可以卡过QAQ,然而不会CDQ,于是下午学了一学,还是比较好学的。
然而这还不是高潮!高潮在:这货可以降到一维,然后O(nlogn)轻松过 QAQ
对于任意一个符合条件的(x,y)只会有一种情况(在把A,B,C看成一样的情况下):

A[x] < A[y] 
B[x] > B[y]
C[x] > C[y]

然后不难发现,如果我们把[A,B]&[A,C]拿出来统计一次逆序对的话,这货相当于每一个符合要求的(x,y)被算了2次
于是,跑三遍一维逆序对就好了QAQ 这个能算简单的容斥吗?

BIT + 线段树:http://paste.ubuntu.com/18236197/
CDQ分治:http://paste.ubuntu.com/18236240/
逆序对虐场代码:

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

const int MAXN = 200000+9;

int n,a[MAXN],b[MAXN],c[MAXN],ord[MAXN];
LL vout;

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define low(x) (x&(-x))
	int arr[MAXN],sum;
	
	inline void init(){
		memset(arr,0,sizeof(arr));
		sum = 0;}
	
	inline void modify(int pos){
		for (int i=pos;i<=n;i+=low(i))
			arr[i] += 1; sum++;
	} 
	
	inline int query(int pos){
		int ret = 0;
		for (int i=pos;i;i-=low(i))
			ret += arr[i];
		return sum-ret;
	}
};

inline void itv(int *A, int *B){
	BIT::init();
	for (int i=1;i<=n;i++) ord[A[i]] = i;
	for (int j=1,i=ord[j];j<=n;i=ord[++j])
		vout += BIT::query(B[i]),
		BIT::modify(B[i]);
}

int main(){
	freopen("contest.in","r",stdin);
	freopen("contest.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	itv(a,b); itv(b,c); itv(a,c); 
	printf("%lld\n",vout/2LL);
	return 0;
}

另外,这题做的时候,发现对于小的结构体,貌似直接排序比排指针还要快一点QAQ
可能是因为后期指针寻址也要花时间吧!所以以后CDQ就直接结构体写了吧! 有图有真相:
struct_iterator

【BZOJ 3790】神奇项链

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3790
离线版题目:http://paste.ubuntu.com/17470379/
吐槽:板题,直接上代码不解释

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 120000;

char pat[MAXN],chr[MAXN];
int n,l[MAXN],r[MAXN],len[MAXN],ord[MAXN];

namespace FenwickTree{
	#define BIT FenwickTree
	#define low(x) (x&(-x))
	#define INF 1000000000
	int arr[MAXN],buf[MAXN];

	inline void init(){
		for (int i=1;i<=n;i++)
			arr[i] = buf[i] = INF;
	}

	inline int query(int left, int right){
		if (right < left) return INF; else { int ret = INF; while (right >= left){
				if (right-low(right)+1>=left) ret = min(ret,arr[right]),right-=low(right);
				else ret = min(ret,buf[right]), right--;
			}
			return ret;
		}
	}

	inline void modify(int pos, int nv){
		if (buf[pos] > nv) {
			buf[pos] = nv;
			for (int i=pos;i<=n;i+=low(i)) if (arr[i] > nv) arr[i] = nv;
				else break;
		} else return;
	}
};

inline bool sort_cmp(const int &A, const int &B){
	return r[A] < r[B];
}

inline int manacher(){
	int m=n*2+1,itr=0;
	for (int i=1;i<=n;i++)
		chr[i*2-1] = '@',
		chr[i*2] = pat[i];
	chr[m] = '@'; chr[m+1] = '#'; chr[0] = '$';

	for (int i=1,p1,p2;i<=m;i++){ if (itr+len[itr] > i)  len[i] = min(len[2*itr-i],itr+len[itr]-i);
		else len[i] = 0;
		p1 = i-len[i]; p2 = i+len[i];
		while (chr[--p1] == chr[++p2]) len[i]++;
		if (itr+len[itr] < i+len[i]) itr = i;
	}

	for (int i=1;i<=m;i++)
		r[i] = i+len[i],
		l[i] = i-len[i],
		ord[i] = i;
	sort(ord+1,ord+m,sort_cmp);

	n = m; BIT::init(); BIT::modify(1,0);
	for (int j=1,i=ord[j],tmp;j<=n;j++,i=ord[j]){
		tmp = BIT::query(l[i],r[i]-1)+1;
		BIT::modify(r[i],tmp);
	}

	return BIT::query(m-1,m)-1;
}

int main(){
	while (~scanf("%s",pat+1)){
		n = strlen(pat+1);
		printf("%dn",manacher());
	}
	return 0;
}