1.bit
#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define lowBit(S) (S & (-S))
#define setAll(S, n) (S = (1 << n) - 1)
#define modulo(S, N) ((S) & (N - 1)) // returns S % N, where N is a power of 2
#define isPowerOfTwo(S) (!(S & (S - 1)))
#define nearestPowerOfTwo(S) ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))
#define turnOffLastBit(S) ((S) & (S - 1))
#define turnOnLastZero(S) ((S) | (S + 1))
#define turnOffLastConsecutiveBits(S) ((S) & (S + 1))
#define turnOnLastConsecutiveZeroes(S) ((S) | (S - 1))
2.UF
#include<iostream>
#include<vector>
#define FOR(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
using namespace std;
typedef vector<int> vi;
vi p,rank;
void build(int N){
p.assign(N,0);//import
FOR(i,0,N+1) p[i] = i;
rank.assign(N,0);
}
void link(int i,int j){
if(p[i]==p[j]) return ;
if(rank[i] < rank[j]){
p[i] = j;
}
else{
p[j] = i;
if(rank[i] == rank[j])
rank[i]++;
}
}
int find(int i){
return p[i] == i ? i : find(p[i]);
}
bool same(int i,int j){
return find(i) == find(j);
}
int main(){
build(5);
link(2,3);
cout << p[2] << " " << p[3] << endl;
cout << same(2,3) << endl;
cout << find(2) << " " << find(3) << endl;
return 0;
}
3.ST
#include<iostream>
#include<vector>
#define FOR(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
#define lc(p) (p)<<1
#define rc(p) ((p)<<1)+1
using namespace std;
typedef vector<int> vi;
vi st,a;
int n;
void initST(vi &b){
a = b; n = b.size();
st.assign(4*n,0);
}
int build(int p,int L,int R){//1,0,n-1
if(L == R) return st[p] = L; //base1
else{
int v1 = build(lc(p),L,(L+R)/2);
int v2 = build(rc(p),(L+R)/2+1,R);
return st[p] = v1 < v2 ? v1:v2; //base2,/********NOTE***/
}
}
int rmq(int p,int L,int R,int i,int j){
if(L > j || R < i) return -1;
if(L >= i && R <= j) return st[p];//trivial condition
//
int p1 = rmq(lc(p),L,(L+R)/2,i,j);
int p2 = rmq(rc(p),(L+R)/2+1,R,i,j);
if(p1 == -1) return p2;
if(p2 == -1) return p1;
return a[p1] < a[p2] ? p1 : p2;
}
int rmq(int i,int j){
return rmq(1,0,n-1,i,j);
}
int main(){
int arr[] = {0,1,2,3,4,5,6,7,8,9}; vi b(&arr[0],&arr[9]);
initST(b);
//a.assign(10,0); FOR(i,0,10) a[i] = i; st.assign(4*10,0); n = 10;//init
build(1,0,10-1);
cout << st[1] << " " << st[3] << endl;
cout << rmq(0,3) << " " << rmq(1,3) << " " << rmq(3,5) << endl;
return 0;
}
Trie
struct trie{
int id;
trie *next[10];//仅用于存储数字，自行扩展
Node(){
id = -1;
for(i,0,10){
next[i] = NULL;
}
}
};
trie *root = new trie();
void add(char *str,int id){
int len = strlen(str);
trie *u = root;
f(i,0,len){
int v = str[i]-'0';
if(!u->next[v])
u->next[v] = new trie();
u = u->next[v];
if(u->id == -1) //NOTE:首先出现者占有ID
u->id = id;
}
}
int query(char *str){
trie *u = root;
int len = strlen(str);
f(i,0,len){
u = u->next[str[i]-'0'];
if(!u) return -1;
}
return u->id;
}
Fenwick Tree
int v[32003]; //N
int lowbit(int a){
return a&(-a);
}
void update(int r){
while(r<=32000){
v[r]++;
r+=lowbit(r);
}
}
int sum(int r){
int k = 0;
while(r>0){
k+=v[r];
r-=lowbit(r);
}
k+=v[r];//
return k;
}
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#define lowbit(b) (b)&(-b)
using namespace std;
vector<int> ft;
int n;
void init(int n){
ft.assign(n+1,0);
}
int rsq(int b){
int sum = 0;
while(b){
sum+=ft[b];
b-=lowbit(b);
}
return sum;
}
int rsq(int a,int b){
if(a-1) return rsq(b)-rsq(a-1);
return rsq(b);
}
void update(int k,int v){
while(k<ft.size()){
ft[k]+=v;
k+=lowbit(k);
}
}
int main(){
int f[] = {2,4,5,5,6,6,6,7,7,8,9};
n = 10;//0-based
init(n);
for(int i = 0; i < 11; i++)
update(f[i],1);
cout << rsq(1,1) << endl;//ft[1]
cout << rsq(1,2) << endl;//ft[2]
cout << rsq(1,6) << endl;//ft[6]+ft[4] = 5+2
cout << rsq(1,10) << endl;//ft[10]+ft[8] = 1+10
cout << rsq(3,6) << endl;//rsq(1,6)-rsq(1,2)
update(5,2);
cout << rsq(1,10) << endl;
return 0;
}
FT(2D)
POJ1195
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#define lowbit(b) (b)&(-b)
using namespace std;
int ft[1100][1100];
int n,x,y,m,l,b,r,t;
void init(){
memset(ft,0,sizeof ft);
}
int rsq(int x,int y){
int sum = 0;
for(int i = x; i; i -= lowbit(i)){
for(int j = y; j; j -= lowbit(j)){
sum+=ft[i][j];
}
}
return sum;
}
int rsq(int l,int b,int r,int t){
return rsq(r,t)-rsq(r,b-1)-rsq(l-1,t)+rsq(l-1,b-1);
}
void update(int x,int y,int v){
for(int i = x; i <= n; i += lowbit(i)){
for(int j = y; j <= n; j += lowbit(j)){
ft[i][j] += v;
}
}
}
int main(){
int op;
while(scanf("%d",&op)!=EOF){
if(op==3) continue;
else if(op==0){
scanf("%d",&n);
init();
}
else if(op==1){
scanf("%d%d%d",&x,&y,&m); x++;y++;
update(x,y,m);
}
else{
scanf("%d%d%d%d",&l,&b,&r,&t); l++;b++;r++;t++;
printf("%d\n",rsq(l,b,r,t));
}
}
return 0;
}