karriganasta's blog

前言

bitset不止一次听大爷们安利过了…

似乎挺厉害的.
因为bool数组在用的时候只能够用一个byte但是byte有8个bit,0/1只要1个就够了.. 所以浪费了7个bit.

Reference:

~~hfq is so toxic.!~~

#include<bits/stdc++.h>
#include<bitset>
using namespace std;

int main(int argc, char *argv[])
{
	//正常的构造 
	bitset<8>a(42); //[0,0,1,0,1,0,1,0]
	cout << a << endl;
	bitset<70>b(LLONG_MAX); 
	cout << b << endl;
	
	//字符串string构造
	string bit_s = "110010";
	bitset<8>c(bit_s);
	cout << c << endl;
	// bitset<sz>b(bit_string,x,(y));
	bitset<8>d(bit_s,2); //字符串的第 x+1(下标为x)个及之后的甩进bitset.
	cout << d << endl;
	bitset<8>e(bit_s,0,3); //字符串的第 x+1(下标为x) 及共y个甩进bitset. 
	cout << e << endl; 
	
	// string的自定义构造0,1串
	string bit_as = "HHHJJJHHJH";
	bitset<10>f(bit_as,0,bit_as.size(),'H','J'); //把H设为0，J设为1,如果出现了其他的字符就返回错误 
	cout << f << endl; 
	return 0;
}

Atcoder Grand Contest AGC 020 C Median Sum

AGC 020C

水题(~~我还是不会做~~)

用bitset维护一个类似背包的东西..

#include<bits/stdc++.h>
using namespace std;
int n,ret = 0;
bitset<4000010>f;
inline int read(void)
{
	int x = 0,f = 1; char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x*f;
}

int main(int argc, char *argv[])
{
	n = read();
	f[0] = 1;
	while(n--)
	{
		int x = read();
		f = f|(f<<x);
		ret += x;
	}
	int i;
	for (i = (ret+1)/2; !f[i]; i++);
	cout << i;
	return 0;
}

Treap/Splay/Scapegoat板子

全指针毕竟指针好写好调（虽然占多了点M

Treap(LUOGU P3369/BZOJ 3224可食用)

// m     操作有m个
// 1 x   插入元素x
// 2 x   删除元素x。如果成功，输入1，否则输出0
// 3 k   输出值x的“名次”，即比x小的结点个数加1
// 4 x   第k小元素。k=1为最小元素
// 5 x   prefix of x
// 6 x   suffix of x
// ... to be continued ...
#include<bits/stdc++.h>
using namespace std;
struct Node {
	Node *ch[2]; // 左右子树
	int r; // 随机优先级
	int v; // 值
	int s; // 结点总数
	Node(int v = 0):v(v) {
		ch[0] = ch[1] = NULL;
		r = rand();
		s = 1;
	}
	int cmp(int x) const {
		if (x == v) return -1;
		return x < v ? 0 : 1;
	}
	void maintain() {
		s = 1;
		if(ch[0] != NULL) s += ch[0]->s;
		if(ch[1] != NULL) s += ch[1]->s;
	}
};
void rotate(Node* &o, int d) {
	Node* k = o->ch[d^1];
	o->ch[d^1] = k->ch[d];
	k->ch[d] = o;
	o->maintain();
	k->maintain();
	o = k;
}
void insert(Node* &o, int x) {
	if(o == NULL) o = new Node(x);
	else {
		int d = (x < o->v ? 0 : 1);
		insert(o->ch[d], x);
		if(o->ch[d]->r > o->r) rotate(o, d^1);
	}
	o->maintain();
}
Node* find(Node* o, int x) {
	if(o == NULL) return NULL;
	if(x == o->v) return o;
	return x < o->v ? find(o->ch[0], x) : find(o->ch[1], x);
}
void remove(Node* &o, int x) {
	int d = o->cmp(x);
	if(d == -1) {
		Node* u = o;
		if(o->ch[0] != NULL && o->ch[1] != NULL) {
			int d2 = (o->ch[0]->r > o->ch[1]->r ? 1 : 0);
			rotate(o, d2);
			remove(o->ch[d2], x);
		} else {
			if(o->ch[0] == NULL) o = o->ch[1];
			else o = o->ch[0];
			delete u;
		}
	} else
		remove(o->ch[d], x);
	if(o != NULL) o->maintain();
}
int kth(Node* o, int k) {
	if(o == NULL || k <= 0 || k > o->s) return 0;
	int s = (o->ch[0] == NULL ? 0 : o->ch[0]->s);
	if(k == s+1) return o->v;
	else if(k <= s) return kth(o->ch[0], k);
	else return kth(o->ch[1], k-s-1);
}
int rank(Node* o, int x) {
	if(o == NULL) return 1;
	if(x <= o->v) return rank(o->ch[0], x);
	return rank(o->ch[1], x) + (o->ch[0] == NULL ? 0 : o->ch[0]->s) + 1;
}
int prefix(Node *o, int k,int c) {
	if (o == NULL) return c;
	if (k > o->v) return prefix(o->ch[1],k,o->v);
	else return prefix(o->ch[0],k,c);
}
int suffix(Node *o, int k,int c) {
	if (o == NULL) return c;
	if (k < o->v) return suffix(o->ch[0],k,o->v);
	else return suffix(o->ch[1],k,c);
}
const int INF = INT_MAX >> 1;
/*
void dfs(Node *o)
{
	if (o == NULL) return ;
	printf("%d\n",o->v);
	 printf("LC of %d:\n",o->v);dfs(o->ch[0]);
	 printf("RC of %d:\n",o->v); dfs(o->ch[1]);
	printf("EO %d!\n\n",o->v); 
}
*/
int main(int argc, char *argv[]) {
	srand(int(time(NULL)));
	int m, c, v;
	Node* root = new Node(INF);
	scanf("%d", &m);
	while(m--) 
	{
		scanf("%d%d", &c, &v);
		if(c == 1) insert(root, v);
		else if(c == 2) {
			Node* o = find(root, v);
			if(o != NULL) remove(root, v);
		} else if(c == 3) printf("%d\n", rank(root, v));
		else if(c == 4) printf("%d\n", kth(root,v));
		else if(c == 5) printf("%d\n",prefix(root,v,0));
		else printf("%d\n",suffix(root,v,0));
	}
	return 0;
}

Splay(LUOGU P3391/BZOJ 3223可食用)

(好像叫Spaly的也有大雾)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10; 
struct Node {
	Node* ch[2];
	int v,s,flip;
	int cmp(int k) {
		int d=k-ch[0]->s;
		if(d==1) return -1;
		return d<=0? 0:1;
	}
	void maintain() {
		s=ch[0]->s+ch[1]->s+1;
	}
	void pushdown() {
		if(flip) {
			flip=0;
			swap(ch[0],ch[1]);
			ch[0]->flip^=1;
			ch[1]->flip^=1;
		}
	}
};
Node* null=new Node();
void rotate(Node* &o,int d) {
	Node* k=o->ch[d^1];
	o->ch[d^1]=k->ch[d];
	k->ch[d]=o;
	o->maintain(),k->maintain();
	o=k;
}
void splay(Node* &o,int k) {
	o->pushdown();
	int d=o->cmp(k);
	if(d==1) k-=o->ch[0]->s+1;
	if(d!=-1) {
		Node* p=o->ch[d];
		p->pushdown();
		int d2=p->cmp(k);
		int k2=d2==0? k:k-p->ch[0]->s-1;
		if(d2!=-1) {
			splay(p->ch[d2],k2);
			if(d==d2) rotate(o,d^1);
			else rotate(o->ch[d],d);
		}
		rotate(o,d^1);
	}
}
Node* merge(Node* left,Node* right) {
	splay(left,left->s);
	left->ch[1]=right,left->maintain();
	return left;
}
void split(Node* o,int k,Node* &left,Node* &right) {
	splay(o,k);
	left=o,right=left->ch[1],left->ch[1]=null;
	left->maintain();
}
struct SplaySequence {
	int n;
	Node seq[maxn];
	Node* root;

	Node* build(int sz) {
		if(!sz) return null;
		Node* l=build(sz/2);
		Node* o=&seq[++n];
		o->v=n;
		o->ch[0]=l;
		o->ch[1]=build(sz-sz/2-1);
		o->flip=o->s=0;
		o->maintain();
		return o;
	}
	void init(int sz) {
		n=null->s=0;
		root=build(sz);
	}
} spaly;
vector<int> ans;
void print(Node* o) {
	if(o!=null) {
		o->pushdown();
		print(o->ch[0]);
		ans.push_back(o->v);
		print(o->ch[1]);
	}
}

int read() {
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	int x=0;
	while(isdigit(c)) {
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
int n,m;
int main(int argc, char *argv[]) 
{
	n=read(),m=read();
	spaly.init(n+1);   
	int l,r;
	Node *left,*right,*mid;
	while(m--) {
		l=read(),r=read();
		split(spaly.root,l,left,right);
		split(right,r-l+1,mid,right);
		mid->flip^=1;
		spaly.root = merge(merge(left,mid),right);
	}
	print(spaly.root);
	for(int i=1; i<ans.size(); i++) printf("%d ",ans[i]-1);
	return 0;
}

Scapegoat(LUOGU P3369/BZOJ 3224可食用)

#include<bits/stdc++.h>
#include<vector>
using namespace std;
const double alpha=0.7;

struct scapegoat{
    scapegoat *l,*r;
    int val,size,cnt;
    bool deleted;
    bool is_bad(){return (l->cnt > alpha*cnt+5 || r->cnt > alpha*cnt+5);}
    void maintain(){size=!deleted+l->size+r->size; cnt=1+r->cnt+l->cnt;}
};
scapegoat *null;

void dfs(scapegoat *o,vector<scapegoat*> &v)
{
    if(o == null) return;
    dfs(o->l,v);
    if(!o->deleted) v.push_back(o);
    dfs(o->r,v);
    if(o->deleted) delete o;
}
scapegoat *build(vector<scapegoat*> &v,int l,int r)
{
    if(l >= r) return null;
    int mid = (l+r) >> 1;
    scapegoat *o = v[mid];
    o->l = build(v,l,mid);
    o->r = build(v,mid+1,r);
    o->maintain();
    return o;
}
void rebuild(scapegoat* &o)
{
    vector<scapegoat*> v;
    dfs(o,v);
    o = build(v,0,v.size());
}
void insert(int x,scapegoat* &o)
{
    if(o==null)
    {
        o=new scapegoat;
        o->l=o->r=null;
        o->deleted=false;
        o->size=o->cnt=1;
        o->val=x;
        return;
    }
    else
    {
        ++o->size;
        ++o->cnt;
        if(x>=o->val)
            insert(x,o->r);
            else
            insert(x,o->l);
        if(o->is_bad())rebuild(o);
    }
}
int rank(scapegoat *now,int x)
    {
        int ans=1;
        while(now!=null)
        {
            if(now->val>=x)now=now->l;
            else
            {
                ans+=now->l->size+!now->deleted;
                now=now->r;
            }
        }
        return ans;
    }
int kth(scapegoat *now,int x)
{
    while(now!=null)
    {
        if(!now->deleted && now->l->size+1==x)
            return now->val;
        if(now->l->size>=x)now=now->l;
            else
            {
                x-=now->l->size+!now->deleted;
                now=now->r;
            }
    }
}
void erase(scapegoat *o,int rk)
{
    if(!o->deleted && rk==o->l->size+1)
    {
        o->deleted=1;
        --o->size;
        return;
    }
    --o->size;
    if(rk<=o->l->size+!o->deleted)
        erase(o->l,rk);
    else
        erase(o->r,rk-o->l->size-!o->deleted);
}
inline void read(int &a)
{
    int negativ = 1;
    a = 0;
    char c = getchar();
    while(!isdigit(c)){if(c == '-') negativ = -1; c = getchar();} 
    while(isdigit(c)) {a = a*10+c-'0';c = getchar();}
    a *= negativ;
}

scapegoat *root;
int main(int argc, char *argv[])
{
    null = new scapegoat;
    root = null;
    int n;
    read(n);
    while(n--)
    {
        int op,x;
        read(op); read(x);
        if(op==1)insert(x,root);
        if(op==2)erase(root,rank(root,x));
        if(op==3)printf("%d\n",rank(root,x));
        if(op==4)printf("%d\n",kth(root,x));
        if(op==5)printf("%d\n",kth(root,rank(root,x)-1));
        if(op==6)printf("%d\n",kth(root,rank(root,x+1)));
    }
    return 0; 
}

「树链剖分 - 学习笔记」

「Codeforces」CF-Round485 Div2 复盘

链接

浅谈次小生成树

次小生成树

定义

[资瓷新域名辣！欢迎使用karriganasta.xyz访问]

ZJOI2018酱油记

「HR(HackerRank)」斯波题切题记

引言

[奇技淫巧] bitset大法吼啊

前言

Atcoder Grand Contest AGC 020 C Median Sum

Treap/Splay/Scapegoat 学习笔记&板子

Treap(LUOGU P3369/BZOJ 3224可食用)

Splay(LUOGU P3391/BZOJ 3223可食用)

Scapegoat(LUOGU P3369/BZOJ 3224可食用)

Atcoder Regular Contest arc 091-092 切(W)题(A)记

概述

生成函数学习笔记[干货]

概论