编织幻梦

这坑爹玩意……这样能删能插了。。

ps:我居然把分裂点看反了！！

pps:删除节点之后我居然忘记上传了！！（虽然按照这颗树的尿性很快就会上传上去。。）

代码有错……nth_element是左闭右开的

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const double eps=1e-12;
const int poolsize = 10000;
const double alpha = 0.7;
class kdtree
{
public:
	struct pointF
	{
		double d[2];
		inline bool operator == (const pointF &a){
			return (abs(a.d[0]-d[0])<=eps && abs(a.d[1]-d[1])<=eps);
		}
	};
private:
	struct node
	{
		kdtree *t;
		pointF split_node;
		int split_method;
		node*ch[2];
		node*left(){return ch[0];}; // < split_pos
		node*right(){return ch[1];};// > split_pos
		int size;
		bool exist;
		void rebuild();
		void rebuild_dfs(node *n,pointF* ps,int &size);
		bool judge(){
			if (!ch[0]||!ch[1]) return false;
			return !size || ch[0]->size > alpha * size || ch[1]->size > alpha * size;
		};
		node(){
			size=1;
			exist=true;
			//if (judge()) rebuild(); 
		}

	}*top,node_pool[poolsize],*alloca_reuse[poolsize];int pool;int stack_size;

	node * alloca_node(){
		if (stack_size){
			// 优先从回收池中取出
			node_pool[stack_size].t = this;node_pool[stack_size].size=1;node_pool[stack_size].exist=true;
			return alloca_reuse[stack_size--];
		}
		else
		{
			node_pool[pool].t = this;node_pool[pool].size=1;node_pool[pool].exist=true;
			return &node_pool[pool++];
		}
	};
	void release_node(node *n){
		memset(n,0,sizeof(node));
		alloca_reuse[stack_size++]=n;
	};
public:
	void build(pointF *_ps,int _size); // ps => [1,n]
	pointF search(pointF x);
	kdtree(){
		top=0;pool=0;ps=0;builded=false;sort_by=0;stack_size=0;
		memset(node_pool,0,sizeof(node_pool));
		memset(alloca_reuse,0,sizeof(alloca_reuse));
	};
	void clean(){
		top=0;pool=0;ps=0;builded=false;sort_by=0;stack_size=0;
		memset(node_pool,0,sizeof(node_pool));
		memset(alloca_reuse,0,sizeof(alloca_reuse));
		
	};
	void clean_fast(){
		top=0;pool=0;ps=0;n=0;builded=false;sort_by=0;stack_size=0;
		memset(node_pool,0,sizeof(node_pool));
		memset(alloca_reuse,0,sizeof(alloca_reuse));
	};
	bool remove(pointF p);
	void insert(pointF p);
	void select(pointF lt,pointF rb,vector<pointF> &target);
private:
	pointF *ps;
	pointF filter;
	pointF result;
	bool builded;
	int n;
	node* build_dfs(int l,int r);
	void search_dfs(node* n,bool force,bool lazy);
	void insert_dfs(node* n,bool mt,bool re_lazy);
	void select_dfs(node* n,pointF <,pointF& rb,vector<pointF> &target);
	node *ansp;
	double ansd;
	inline double Variance(int l,int r,int d){
		double variance = 0;
		double Average = 0;
		for (int i=l;i<=r;i++) Average+=ps[i].d[d];
		Average/=(r-l+1.0);
		for (int i=l;i<=r;i++) variance+=(ps[i].d[d]-Average)*(ps[i].d[d]-Average);
		variance/=(r-l+1.0);
		return variance;
	};
	int sort_by;
	class sort_compare{
	private:
		int sort_by;
	public:
		bool operator()(const pointF & x, const pointF & y){
			return x.d[sort_by]<y.d[sort_by];
		};
		sort_compare(int _sort_by){
			sort_by=_sort_by;
		}
	};	
	inline double distance(const pointF & x,const pointF & y){
		return (x.d[0]-y.d[0])*(x.d[0]-y.d[0]) +  (x.d[1]-y.d[1])*(x.d[1]-y.d[1]);
	}
}T;
void kdtree::build(pointF *_ps,int _size){
	if (builded) throw "Cannot build a kd-tree again before you clean it!!";
	builded=true;
	ps=_ps;n=_size;
	top=build_dfs(1,n);
};
kdtree::node* kdtree::build_dfs(int l,int r){ // [l,r]
	if (r-l<0) return NULL;
	node * range = alloca_node();range->exist=true;
	int mid = (l+r)>>1;
	double VarianceX = Variance(l,r,0);
	double VarianceY = Variance(l,r,1);
	int split_method_i = VarianceY>VarianceX;
	range->split_method = split_method_i;
	sort_by = split_method_i;
	nth_element(ps+l,ps+mid,ps+r+1,sort_compare(sort_by));
	//sort(ps+l,ps+r,sort_compare(sort_by));
	range->split_node = *(ps+mid);
	range->ch[0]= build_dfs(l,mid-1);
	range->ch[1]= build_dfs(mid+1,r);
	range->size = ((range->ch[0])?(range->ch[0]->size):(0))+((range->ch[1])?(range->ch[1]->size):(0)) + (range->exist);
	return range;
};
kdtree::pointF kdtree::search(pointF x){
	if (!builded) throw "Cannot work on empty tree!!";
	filter=x;
	ansd = 1e307;
	search_dfs(top,false,false);
	return ansp->split_node;
};
bool kdtree::remove(pointF x){
	/* 刚调整过，本来删完忘记上传size修改了，这样应该可以……
	 *	但是一次修改造成的不平衡只有下次访问到才会修复……
	 */
	if (!builded) throw "Cannot work on empty tree!!";
	filter=x;
	ansd = 1e307;
	search_dfs(top,true,false);
	return ansd==0;
}
void kdtree::search_dfs(node* n,bool force,bool lazy){
	if (!n) return ;
	double dist=0;
	dist =distance(n->split_node,filter);
	if ((dist<ansd && n->exist && !force) || (force && n->split_node==filter)){
		ansd=dist;
		ansp=n;
		if (force) {
			ansp->exist=false;
			ansp->size--;
			return;
		}
	}
	int sm=n->split_method;
	bool rebuild=n->judge();
	double radius = (filter.d[sm]-n->split_node.d[sm])*(filter.d[sm]-n->split_node.d[sm]);
	if (filter.d[sm]-n->split_node.d[sm]<=eps){
		// left
		search_dfs(n->ch[0],force,lazy|rebuild);
		if (ansd<=radius) search_dfs(n->ch[1],force,lazy|rebuild);
	}else{
		// right
		search_dfs(n->ch[1],force,lazy|rebuild);
		if (ansd<=radius) search_dfs(n->ch[0],force,lazy|rebuild);
	}
	n->size = ((n->ch[0])?(n->ch[0]->size):(0))+((n->ch[1])?(n->ch[1]->size):(0)) + (n->exist);
	if (rebuild &!lazy) n->rebuild(); // 重构这棵树
}

void kdtree::insert(pointF p){
	filter = p;
	insert_dfs(top,0,0);
}

void kdtree::insert_dfs(node* n,bool mt,bool re_lazy){
	/*
	 *	同样……一次修改之后不会马上重构。。
	 */
	int sm=n->split_method;
	double radius = (filter.d[sm]-n->split_node.d[sm])*(filter.d[sm]-n->split_node.d[sm]);
	bool re=n->judge();
	int belong = (filter.d[sm]-n->split_node.d[sm]>=eps);  //target.pos>split => 1
	if (n->ch[belong]!=NULL){
		insert_dfs(n->ch[belong],!mt,re|re_lazy);
	}else{
		n->ch[belong]=alloca_node();
		n->ch[belong]->split_method = mt;
		n->ch[belong]->split_node = filter;
	}
	n->size = ((n->ch[0])?(n->ch[0]->size):(0))+((n->ch[1])?(n->ch[1]->size):(0)) + (n->exist);
	if (!re_lazy && re) n->rebuild();
};
void kdtree::node::rebuild(){
	int size=1;
	rebuild_dfs(this,t->ps,size);size--;
	node *va = t->build_dfs(1,size);
	memcpy(this,va,sizeof(node));
	t->release_node(va);
};
void kdtree::node::rebuild_dfs(node *n,pointF* ps,int &size){
	if (!n) return;
	if (n->exist){
		ps[size++]=n->split_node;
	}
	rebuild_dfs(n->ch[0],ps,size);
	rebuild_dfs(n->ch[1],ps,size);
	if (n!=this) t->release_node(n);
};
void kdtree::select(pointF lt,pointF rt,vector<pointF> &target){
	select_dfs(top,lt,rt,target);
};
void kdtree::select_dfs(node* n,pointF <,pointF &rb,vector<pointF> &target){
	/*
	 *	关于这里的lt、rb或许重构为degree的范围更好？
	 */
	if (!n) return;
	if (n->size==0) return ;
	pointF p = n->split_node;
	if (n->exist && p.d[0]>=lt.d[0] && // 大于左上的x
					p.d[0]<=rb.d[0] && // 小于右下的x
					p.d[1]<=lt.d[1] && // 小于左上的y
					p.d[1]>=rb.d[1])   // 大于右下的y
					target.push_back(p);
	if (n->split_method==0){
		if (lt.d[0] <= p.d[0]) select_dfs(n->ch[0],lt,rb,target); // left
		if (rb.d[0] >= p.d[0]) select_dfs(n->ch[1],lt,rb,target); // right
	} else {
		if (rb.d[1] <= p.d[1]) select_dfs(n->ch[0],lt,rb,target); // bottom
		if (lt.d[1] >= p.d[1]) select_dfs(n->ch[1],lt,rb,target); // top
	}
};
kdtree::pointF points[500]; // buffers
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++) scanf("%lf%lf",&points[i].d[0],&points[i].d[1]);
	T.build(points,n);
	while (q--){
		kdtree::pointF lt;
		kdtree::pointF rt;
		int x;scanf("%d",&x);
		if (x==1){
			scanf("%lf%lf",<.d[0],<.d[1]);
			scanf("%lf%lf",&rt.d[0],&rt.d[1]);
			vector<kdtree::pointF> v;
			T.select(lt,rt,v);
			for (vector<kdtree::pointF>::iterator it=v.begin();it!=v.end();it++)
				printf("(%.2lf %.2lf)\n",it->d[0],it->d[1]);
		}else{
			scanf("%lf%lf",<.d[0],<.d[1]);
			if (x==2)
				T.remove(lt);
			else
				T.insert(lt);
		}
	}
	system("pause");
};

复习中……还是zkw代码量少啊。。

#include <cstdio>
#include <algorithm>
using namespace std;
struct normal_tree{
	struct node{
		int l,r;
		int cmax,cmin;
		node *ch[2];
		inline bool range(int x){
			return (x>=l&&x<=r);
		}
		inline pair<int,int> range(int x,int y){
			pair<int,int> rst;
			rst.first = max(x,l);
			rst.second = min(y,r);
			return rst;
		}
	}*top,pool[(1<<18)+2];int ps;
	int query_max(int l,int r);
	int query_min(int l,int r);
	int query_max_dfs(int l,int r,node * f);
	int query_min_dfs(int l,int r,node * f);
	void change(int x,int value);
	void change_dfs(int x,int value,node * f);
	void build(int n); // [0,n]
	void build(int l,int r,node* f);
	node* node_alloc(int l,int r){pool[ps].l=l,pool[ps].r=r;return &pool[ps++];};
	normal_tree(){ps=0;top=0;memset(pool,0,sizeof(pool));}
}T;
void normal_tree::build(int n){
	top=node_alloc(0,n);
	build(0,n,top);
}
void normal_tree::build(int l,int r,node* f){
	if (l==r) return;
	f->ch[0]=node_alloc(l,(l+r)/2);
	f->ch[1]=node_alloc((l+r)/2+1,r);
	build(l,(l+r)/2,f->ch[0]);
	build((l+r)/2+1,r,f->ch[1]);
};
void normal_tree::change(int x,int value){
	change_dfs(x,value,top);
};
void normal_tree::change_dfs(int x,int value,node*f){
	if (f->l==x&&f->r==x){
		f->cmax=f->cmin=value;return ;
	};
	if (f->ch[0]->range(x)){
		change_dfs(x,value,f->ch[0]);
		f->cmax = max(f->ch[1]->cmax,f->ch[0]->cmax);
		f->cmin = min(f->ch[1]->cmin,f->ch[0]->cmin);
	}else
	{
		change_dfs(x,value,f->ch[1]);
		f->cmax = max(f->ch[1]->cmax,f->ch[0]->cmax);
		f->cmin = min(f->ch[1]->cmin,f->ch[0]->cmin);
	}
};
int normal_tree::query_max(int l,int r){
	return query_max_dfs(l,r,top);
}
int normal_tree::query_min(int l,int r){
	return query_min_dfs(l,r,top);
};
int normal_tree::query_max_dfs(int l,int r,node * f){
	if (f->l==l&&f->r==r) return f->cmax;
	pair<int,int> t;
	int rst = 0;
	if (f->ch[0]->range(l)){
		t = f->ch[0]->range(l,r);
		rst = max(rst,query_max_dfs(t.first,t.second,f->ch[0]));
	}
	if (f->ch[1]->range(r)){
		t = f->ch[1]->range(l,r);
		rst = max(rst,query_max_dfs(t.first,t.second,f->ch[1]));
	}
	return rst;
}
int normal_tree::query_min_dfs(int l,int r,node * f){
	if (f->l==l&&f->r==r) return f->cmin;
	pair<int,int> t;
	int rst = 0x3fffffff;
	if (f->ch[0]->range(l)){
		t = f->ch[0]->range(l,r);
		rst = min(rst,query_min_dfs(t.first,t.second,f->ch[0]));
	}
	if (f->ch[1]->range(r)){
		t = f->ch[1]->range(l,r);
		rst = min(rst,query_min_dfs(t.first,t.second,f->ch[1]));
	}
	return rst;
};
int main(){
	int n,q;scanf("%d%d",&n,&q);
	T.build(n);//[0,n]
	for (int i=1;i<=n;i++) {
		int x;scanf("%d",&x);T.change(i,x);
	}
	for (int i=1;i<=q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		int rst = T.query_max(l,r)-T.query_min(l,r);
		printf("%d\n",rst);
	}
};

复习中。。。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxh = 17; 
const int maxm = 1<<(maxh-1);
struct zkw_segment{
	int zkw_max[(maxm<<1)+1]; // max
	int zkw_min[(maxm<<1)+1]; // min
	int query_max(int l,int r);
	int query_min(int l,int r);
	void change(int x,int delta);
}T;
int zkw_segment::query_max(int left,int right){
	int ans=-1;
	for (int l=maxm+left-1,r=maxm+right+1;l^r^1;l>>=1,r>>=1){
		if (~l&1) ans=max(ans,zkw_max[l^1]);
		if (r&1) ans=max(ans,zkw_max[r^1]);
	};
	return ans;
};
int zkw_segment::query_min(int left,int right){
	int ans=0x3fffffff;
	for (int l=maxm+left-1,r=maxm+right+1;l^r^1;l>>=1,r>>=1){
		if (~l&1) ans=min(ans,zkw_min[l^1]);
		if (r&1) ans=min(ans,zkw_min[r^1]);
	};
	return ans;
};
void zkw_segment::change(int x,int value){
	int p=maxm+x;
	zkw_max[p]=value;zkw_min[p]=value;p>>=1;
	for (;p!=0;p>>=1){
		zkw_max[p]=max(zkw_max[p<<1],zkw_max[(p<<1)+1]);
		zkw_min[p]=min(zkw_min[p<<1],zkw_min[(p<<1)+1]);
	}
};
int main(){
	int n,q;scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++) {
		int x;scanf("%d",&x);T.change(i,x);
	}
	for (int i=1;i<=q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		int rst = T.query_max(l,r)-T.query_min(l,r);
		printf("%d\n",rst);
	}
};

ruby这个傻×只支持static真心蛋疼←看看人家python。

所以在所有函数外面加个套套。

怎么通过套套找到函数呢？

VALUE obj

通过obj的userdata域。

可是……我的类没有新建啊233。

使用rb_define_alloc_func在类被建立的时候新建C类，然后……设置到Userdata域去。。

WxRuby真是我见过最糟糕的UI库……没有之一，文档写的不全，常数各种难找，有的甚至去翻了相应库的源代码才找到= =好在范例还是挺给力的。

 使用的时候只要 Helper.createStyledTextCtrl(self)即可。部份代码参照了http://wxruby.rubyforge.org/svn/trunk/wxruby/samples/text/scintilla.rb

这个范例。

以及

https://metacpan.org/source/AZAWAWI/Wx-Scintilla-0.20/wx-scintilla2/src/scintilla/src/LexRuby.cxx

LuxRuby的源代码。

require "net/https"
require "uri" 
require 'iconv'
$i=Iconv.new("GBK","UTF-8")
$player=<<EOF
<embed width="950" height="445" flashvars="type2=tudou&id=VIDEOID" pluginspage="http://www.adobe.com/shockwave/download/download.cgi?P1_Prod_Version=ShockwaveFlash" wmode="window" allowscriptaccess="always" allowfullscreen="true" type="application/x-shockwave-flash" src="/newflvplayer/playert.swf" id="ACFlashPlayer"></embed>
EOF
$player=$i.iconv $player
def makePlayer(iid)
	p=$player.clone
	p.gsub(/VIDEOID/){iid}
end
def getlist()
	print $i.iconv "请输入豆单的完整地址（含HTTP://）"
	url=URI.parse gets	
	net=Net::HTTP.new(url.host, url.port)
	r,data = net.get(url.path,{"Referer"=>"www.tuduo.com"})
	data.force_encoding("GBK")
	@str=""
	@mov=[]
	data.gsub(/iid:([0-9]*)/){@mov<<[$1]}#@str<<#makePlayer($1)<<"#" + "p" + "#" + "#{$3}#" + "e" + "#\r\n"}
	i=0
	data.gsub(/,title."([^"]*)"/){@mov[i][1]=$1;i+=1;}
	for i in @mov
		@str<<makePlayer(i[0])<<"#" + "p" + "#" + "#{i[1]}#" + "e" + "#\r\n"
	end
	if $f
		$f.write(@str)
		$f.close
		print $i.iconv "已经保存到文件\n"
		$f=false
	else
		print @str
	end
end
def getOne()
	print $i.iconv "请输入视频的完整地址（含HTTP://）"
	url=URI.parse gets
	net=Net::HTTP.new(url.host, url.port)
	r,data = net.get(url.path,{"Referer"=>"www.tuduo.com"})
	data.force_encoding("GBK")
	@str=""
	@iid=0
	data.gsub(/defaultIid = ([0-9]*)/){@iid=$1}
	data.gsub(/,iid =([^0-9]*)([0-9]*)/){@iid=$2} if @iid==0
	if $f
		$f.write(makePlayer(@iid))
		$f.close
		print $i.iconv "已经保存到文件\n"
		$f=false
	else
		print makePlayer(@iid)
	end
end
func=0
$f=false

while func.to_i!=4
	system('cls')
	print $i.iconv "欢迎使用Tudou视频转贴=>Acfun工具 b3 By yangff\n"
	print $i.iconv "请选择功能\n"
	print $i.iconv "[1] 转贴单个视频（请确认地址是http://www.tudou.com/programs/view/......这样的）\n"
	print $i.iconv "[2] 转贴豆单（请确认地址是http://www.tudou.com/playlist/p/........这样的）\n"
	print $i.iconv "[3] 保存到文件\n"
	print $i.iconv "[4] 退出\n"
	print $i.iconv "\n"
	print $i.iconv "请选择："
	func=gets
	break if func.to_i==4
	if (func.to_i==1)
		getOne
	elsif (func.to_i==2)
		getlist
	elsif (func.to_i==3)
		print $i.iconv "输入保存地址："
		url=gets.strip
		$f=File.open(Iconv.iconv("UTF-8","GBK",url)[0],"w")
		next
	end
	print "\n"
	print $i.iconv "复制上面的代码，在编辑器转入代码编辑后粘贴即可！\n"
	system('pause')
end

坑爹物无误，没有优化，BUG一坨。

Pólya定理

设Ω=[1,n],M={S₁,S₂,…S_m}是m种颜色的集合，对Ω中的元素用M中的颜色着色，得到的图象集合用M^Ω表示，|M^Ω|=mⁿ,每个中的元素都有m种着色可能，n个元的着色有mⁿ种可能。即共有mⁿ个图象。
设G是以Ω为目标记得置换群，是某一转动群R的表示。G是以M^Ω为目标记得置换群，是同一转动群R的表示。

G≌R,G≌R，G≌G
一个着色图象在G的作用下变为另一个图象，则这两个图象属于同一方案。

但是怎么用？？最小割？