【SinGuLaRiTy-1040】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
二维线段树 2D_Segment_Tree
//示例：单点修改，区间求和。
//注意内存限制
#include<cstdio>
#include<iostream>
#include<cstring>
const int MAXN = ;
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
#define M(x,y) (((x)+(y))>>1)
using namespace std;
int N, ans;
struct Node {
short l, r;
int sum;
} a[MAXN*][MAXN*];
int refer[MAXN];
void build_y(int &xid, int i, short l, short r)
{
a[xid][i].l = l;
a[xid][i].r = r;
if (l == r) return;
build_y(xid, L(i), l, M(l,r));
build_y(xid, R(i), M(l,r)+, r);
}
void build_x(int i, short l, short r)
{
a[][i].l = l;
a[][i].r = r;
build_y(i, , , N);
if (l==r) { refer[l]=i; return; }
build_x(L(i), l, M(l,r));
build_x(R(i), M(l,r)+, r);
} void update(int x, int y, int &dt)
{
int i = refer[x], j;
while (i>) {
j = refer[y];
while (j>)
a[i][j].sum += dt, j >>= ;
i >>= ;
}
}
void sum_y(int& xid, int i, int& y1, int& y2)
{
if (a[xid][i].l > y2 || a[xid][i].r < y1)
return;
if (a[xid][i].l >= y1 && a[xid][i].r <= y2)
{
ans += a[xid][i].sum;
return;
}
sum_y(xid, L(i), y1, y2);
sum_y(xid, R(i), y1, y2);
}
void sum_x(int i, int& x1, int& y1, int& x2, int& y2)
{
if (a[][i].l > x2 || a[][i].r < x1)
return;
if (a[][i].l >= x1 && a[][i].r <= x2)
{
sum_y(i, , y1, y2);
return;
}
sum_x(L(i), x1, y1, x2, y2);
sum_x(R(i), x1, y1, x2, y2);
} int main()
{
int op, x1, y1, x2, y2, t;
scanf("%d%d", &N, &N);
build_x(, , N);
while (scanf("%d", &op) && op!=)
{
if (op == )
{
scanf("%d%d%d", &x1, &y1, &t);
update(x1, y1, t);
}
else
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
ans = ;
sum_x(, x1, y1, x2, y2);
printf("%d\n", ans);
}
}
return ;
}
双向队列 deque
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = ; struct Deque
{
int nxt[MAXN], prv[MAXN], stk[MAXN], tp;
int val[MAXN];
int f, b, size, t;
void clear() {
f=b=size=; tp=MAXN-;
for (int i=; i<MAXN; ++i)
nxt[i] = prv[i] = , stk[i] = i;
}
Deque() { clear(); }
void push(bool d, int v)
{
if (!size) { f = b = stk[tp--]; val[f] = v; prv[f]=nxt[f]=; }
else {
t = stk[tp--];
if (d) { nxt[b] = t; prv[t] = b; nxt[t] = ; val[t] = v; b = t;}
else { nxt[t] = f; prv[f] = t; prv[t] = ; val[t] = v; f = t; }
}
++size;
}
void pop(bool d)
{
--size;
if (d) stk[++tp] = b, b = prv[b];
else stk[++tp] = f, f = nxt[f];
}
int front() { return val[f]; }
int back() { return val[b]; }
} q; int main()
{ return ;
}
Splay平衡树 Splay_Tree
#include<iostream>
#include<cstdio>
#include<cstring>
#define Max(a,b) ((a)>(b)?(a):(b))
#define L(x) x->ch[0]
#define R(x) x->ch[1]
using namespace std;
const int MAXN = ; struct Node {
int sz;
Node *fa, *ch[];
Node () { sz=; }
}nil, *NIL=&nil; struct SeqSplay //用来维护区间操作的splay
{
Node a[MAXN], *root;
void init() { root=NIL; }
inline void pushup(Node *x) {
x->sz = L(x)->sz + R(x)->sz + ;//size域一定要维护 }
inline void pushdown(Node *x) {
//标记下放或者左右交换 }
void rotate(Node *x, int d) // 0左1右
{
Node *y = x->fa;
if (y==root) root = x;
pushdown(y); pushdown(x);
y->ch[!d] = x->ch[d];
if (x->ch[d] != NIL)
x->ch[d]->fa = y;
x->fa = y->fa;
if (y->fa != NIL)
y->fa->ch[ y->fa->ch[]==y ] = x;
x->ch[d] = y;
y->fa = x;
pushup(y); pushup(x);
}
void splay(Node*x, Node*target)//双旋至target以下
{
Node *y, *z;
while (x->fa != target) {
y = x->fa; z = y->fa;
pushdown(x);
if (z == target) {
rotate(x, x==y->ch[]);
return;
}
if (y == L(z))
if (x == L(y)) rotate(y, ), rotate(x, );
else rotate(x, ), rotate(x, );
else
if (x == R(y)) rotate(y, ), rotate(x, );
else rotate(x, ), rotate(x, );
pushup(x);
}
}
Node* build(int l, int r, Node* fa)
{
if (l>r) return NIL;
int mid = (l+r)>>;
a[mid].ch[] = build(l, mid-, &a[mid]);
a[mid].ch[] = build(mid+, r, &a[mid]); //此处根据题意具体录入节点内容
pushup(&a[mid]);
return &a[mid];
}
void init(int l, int r) { //伸展树的初始化，外部调用时一定要空置左右端点
root = build(l, r, NIL);
}
void getkth(int k, Node *&target)//将第k个元素旋转至target下面
{
Node *t = root;
while () {
pushdown(t);
if (k == (t->ch[]->sz)+) {
splay(t, target);
return;
}
if (k <= L(t)->sz) t = L(t);
else k-=L(t)->sz+, t = R(t);
}
}
void form(int l, int r) //将区间[l,r]旋转至操作区域
{
getkth(l, root);
getkth(r+, R(root));
} } tree; int main()
{ return ;
}
线段树
struct node
{
int l ,r ,sum ;
}tre[MAXN<<] ; void build(int code,int l,int r)
{
tre[code].l=l ,tre[code].r=r ;
if(l==r)return;
build(code*,l,(l+r)/);
build(code*+,(l+r)/+,r);
} void update(int code,int l,int r)
{
if(l<=tre[code].l&&tre[code].r<=r)
{
//修改
return;
}
//若有懒标记 pushdown();
int mid=(tre[code].l+tre[code].r)/;
if(l<=mid)update(code*,l,r);
if(mid<r)update(code*+,l,r);
//更新 pushup();
tre[code].sum=tre[code*].sum+tre[code*+].sum;
} int query(int code,int l,int r)
{
if(l<=tre[code].l&&tre[code].r<=r)
return tre[code].sum;
int mid=(tre[code].l+tre[code].r)/ ,ans= ;
//pushdown();
if(l<=mid)ans+=query(code*,l,r);
if(mid<r)ans+=query(code*+,l,r);
return ans;
}
二维树状数组
#define LL long long int
#define lowbit(a) ((a)&(-(a)))
LL tre[MAXN+][MAXN+] ;
void update(int a,int b,LL val)
{
val%=mod;
for(;a<=n;a+=lowbit(a))
for(int j=y;j<=m;j+=lowbit(j))
{
tre[i][j]+=val;
if(tre[a][j]>=mod)tre[a][j]-=mod;
}
} LL getsum(int x,int y)
{
LL ans=;
for(;x>;x-=lowbit(x))
for(int j=y;j>;j-=lowbit(j))
{
ans+=tre[x][j];
if(ans>=mod)ans-=mod;
}
return ans;
}
树状数组
#define lowbit(a) ((a)&(-(a)))
#define LL long long int
LL tre[MAXN+] ;
void update(LL a,int pos)
{
a%=mod;
while(pos<=n)
{
tre[pos]+=a;
if(tre[pos]>=mod)tre[pos]-=mod;
pos+=lowbit(pos);
}
} LL getsum(int pos)
{
LL ans= ;
while(pos>)
{
ans+=tre[pos];
if(ans>=mod)ans-=mod;
pos-=lowbit(pos);
}
return ans;
}
并查集
int getroot(int a)
{
if(fa[a]==a)return a;
return fa[a]=getroot(fa[a]);
} void Union(int a,int b)
{
fa[getroot(a)]=getroot(b);
}
归并排序
///归并排序模板。记得和快排一块对着看。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define LL long long
#define inf 0x3f3f3f3f
#define mod 1e9+7
const int maxn=1e5+;
using namespace std;
int temp[maxn];
int num=;///统计逆序对数的。
void Merge(int a[],int left ,int mid,int right)
{
int i=left,j=mid+,n=,length=right-left;///i开始为左半部分最左边，j为右半部分最左边。temp数组是从下标0开始存数。
while(i<=mid&&j<=right){
if(a[i]>a[j]){///左边比右边大。
temp[n++]=a[j++];
num+=mid-i+;///从i到mid都是比a[j]大。
}
else{
temp[n++]=a[i++];
}
}
if(i>mid){///这里说明的是左边全部填满了(因为前面的判断条件是i<=mid，那就是天右边了。
while(j<=right){
temp[n++]=a[j++];
}
}
else{
while(i<=mid){
temp[n++]=a[i++];
}
}
for(int k=;k<=length;k++){///最后赋值到原数组必须要有的。
a[left+k]=temp[k];
}
}
void mergesort(int a[],int left,int right)
{
if(left<right){
int mid=(left+right)/;
mergesort(a,left,mid);
mergesort(a,mid+,right);
Merge(a,left,mid,right);
}
}
int main()
{
int number[] = {};
mergesort(number,,-);///初始化调用也要注意额。 for(int i=;i<;i++){
printf("%d ",number[i]);
}
}
堆排序
int adjust_heap(vector<int> &v, int length, int i){
int left = * i;
int right = * i + ;
int largest = i;
int temp;
while(left < length || right < length){
if (left < length && v[largest] < v[left]){
largest = left;
}
if (right < length && v[largest] < v[right]){
largest = right;
}
if (i != largest){
temp = v[largest];
v[largest] = v[i];
v[i] = temp;
i = largest;
left = * i;
right = * i + ;
}
else{
break;
}
}
}
int build_heap(vector<int> &v, int length){
int i;
int begin = length/ - ; //get the last parent node
for (i = begin; i>=; i--){
adjust_heap(v,length,i);
}
}
int heap_sort(vector<int> &v){
int length = v.size();
int temp;
printline("before sort:",v);
build_heap(v,length);
while(length > ){
temp = v[length-];
v[length-] = v[];
v[] = temp;
length--;
adjust_heap(v,length,);
}
printline("after sort:",v);
}线段树(update:单点增减; query:区间求和) - HDU1166 敌兵布阵
#include <cstdio> #define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = ;
int sum[maxn<<];
void PushUP(int rt) {
sum[rt] = sum[rt<<] + sum[rt<<|];
}
void build(int l,int r,int rt) {
if (l == r) {
scanf("%d",&sum[rt]);
return ;
}
int m = (l + r) >> ;
build(lson);
build(rson);
PushUP(rt);
}
void update(int p,int add,int l,int r,int rt) {
if (l == r) {
sum[rt] += add;
return ;
}
int m = (l + r) >> ;
if (p <= m) update(p , add , lson);
else update(p , add , rson);
PushUP(rt);
}
int query(int L,int R,int l,int r,int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
int m = (l + r) >> ;
int ret = ;
if (L <= m) ret += query(L , R , lson);
if (R > m) ret += query(L , R , rson);
return ret;
}
int main() {
int T , n;
scanf("%d",&T);
for (int cas = ; cas <= T ; cas ++) {
printf("Case %d:\n",cas);
scanf("%d",&n);
build( , n , );
char op[];
while (scanf("%s",op)) {
if (op[] == 'E') break;
int a , b;
scanf("%d%d",&a,&b);
if (op[] == 'Q') printf("%d\n",query(a , b , , n , ));
else if (op[] == 'S') update(a , -b , , n , );
else update(a , b , , n , );
}
}
return ;
}
树的点分治-找出树中有多少点对,满足dis(u,k)<K
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=;
int N,K;
int ans,root,Max;
struct node
{
int v,next,w;
}edge[maxn*];
int head[maxn],tot;
int size[maxn];//树的大小
int maxv[maxn];//最大孩子节点的size
int vis[maxn];
int dis[maxn];
int num;
void init()
{
tot=;
ans=;
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
}
void add_edge(int u,int v,int w)
{
edge[tot].v=v;
edge[tot].w=w;
edge[tot].next=head[u];
head[u]=tot++;
}
//处理子树的大小
void dfssize(int u,int f)
{
size[u]=;
maxv[u]=;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(v==f||vis[v])continue;
dfssize(v,u);
size[u]+=size[v];
if(size[v]>maxv[u])maxv[u]=size[v];
}
}
//找重心
void dfsroot(int r,int u,int f)
{
if(size[r]-size[u]>maxv[u])//size[r]-size[u]是u上面部分的树的尺寸，跟u的最大孩子比，找到最大孩子的最小差值节点
maxv[u]=size[r]-size[u];
if(maxv[u]<Max)Max=maxv[u],root=u;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(v==f||vis[v])continue;
dfsroot(r,v,u);
}
}
//求每个点离重心的距离
void dfsdis(int u,int d,int f)
{
dis[num++]=d;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(v!=f&&!vis[v])
dfsdis(v,d+edge[i].w,u);
}
}
//计算以u为根的子树中有多少点对的距离小于等于K
int calc(int u,int d)
{
int ret=;
num=;
dfsdis(u,d,);
sort(dis,dis+num);
int i=,j=num-;
while(i<j)
{
while(dis[i]+dis[j]>K&&i<j)j--;
ret+=j-i;
i++;
}
return ret;
}
void dfs(int u)
{
Max=N;
dfssize(u,);
dfsroot(u,u,);
ans+=calc(root,);
vis[root]=;
for(int i=head[root];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(!vis[v])
{
ans-=calc(v,edge[i].w);
dfs(v);
}
}
}
int main()
{
while(scanf("%d%d",&N,&K)!=EOF)
{
if(!N&&!K)break;
int u,v,w;
init();
for(int i=;i<N;i++)
{
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
} dfs();
printf("%d\n",ans);
}
return ;
}
Lower_bound & Upper_bound
ForwardIterator my_lower_bound(ForwardIterator beg, ForwardIterator end, T target)
{
ForwardIterator mid;
typename iterator_traits<ForwardIterator>::difference_type count, step; count = distance(beg, end);
while(count > )
{
mid = beg;
step = count/;
advance(mid, step);
if(*mid < target) //mid < target
{
beg = ++mid;
count -= (step+); //count表示当前数组中还有的元素个数
}
else
{
count = step;
}
}
return beg;
}
template<class ForwardIterator, class T>
ForwardIterator my_upper_bound(ForwardIterator beg, ForwardIterator end, T target)
{
ForwardIterator mid;
typename iterator_traits<ForwardIterator>::difference_type count, step; count = distance(beg, end);
while(count > )
{
mid = beg;
step = count/;
advance(mid, step);
if(target < *mid) //mid < target
{
count = step;
}
else
{
beg = ++mid;
count -= (step+);
}
}
return beg;
}
二分查找
//递归版本
int binarySearchRecusion(int* array,int len,int value){
if(len==)
return -; int mid=(len-)/;
if(array[mid]==value)
return mid;
if(array[mid]>value) //在右半区
binarySearchRecusion(array+mid+,len-mid-,value);
else
binarySearchRecusion(array,mid,value); //在左半区
}
//非递归版本
//有序数组递减排列
int binarySearch(int* array,int len,int value){
int mid=;
int low=;
int high=len-;
while(low<=high){
mid=(low+high)/;
if(array[mid]>value){ //在右半区
low=mid+;
continue;
}
else if(array[mid]<value){ //在左半区
high=mid-;
continue;
}else
return mid; //找到
}
return -; //查找失败
}
三分查找
double solve(double MIN,double MAX)
{
double Left, Right;
double mid, midmid;
double mid_value, midmid_value;
Left = MIN;
Right = MAX;
while (Left +eps < Right)
{
mid = (Left + Right) / ;
midmid = (mid + Right) / ;
mid_value = Calc(mid); //Cal()为题意规定的计算内容
midmid_value = Calc(midmid);
///求最大值改成>= 最小值改成<=
if (mid_value >= midmid_value) Right = midmid;
else Left = mid;
}
return Left;
}
Time: 2017-10-17