基礎(chǔ)

基礎(chǔ)算法總結(jié)

進制轉(zhuǎn)化

N 進制轉(zhuǎn)十進制：

long long binary1(string s,int n){//s為輸入N進制，n為進制數(shù)。
	long long p;
	for(int i=0;i<s.size();i++){
		if(s[i]>='A'&&s[i]<='Z')  p=p*n+s[i]-'A'+10;
		else  p=p*n+s[i]-'0';
	}
	return p;
}

十進制轉(zhuǎn) N 進制：

string binary2(int s,int n){
	string a="";
	int p;
	while(s){
		p=s%n;
		if(p>10) a=char(p+55)+a;
		else a=char(p+'0')+a;
		s/=n; 
	}
	return a;
}

質(zhì)數(shù)判斷

bool prime(int a){
	if(a==0||a==1) return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0) return false;
	}
	return true;
}

回文數(shù)判斷

bool palin(int a){
	int s=a;int d=0;
	while(s){
		d=d*10+s%10;
		d/=10;
	}
	if(d==a) return true;
	return false;
}

快讀快寫

inline int read(){//快讀
	int ans=0,j=1;char c=getchar();
	while(c>'9' or c<'0'){if(c=='-')j=-1;c=getchar();}
	while(c>='0' and c<='9'){ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();}
	return ans*j;
}
inline void write(int x){//快寫
	if(x<0){putchar('-');x=-x;}
	if(!x)return;write(x/10);putchar(x%10+'0');
}

高精度

namespace big_number {
	/*
	 * 高精度模板(是vector,所以無限精度)
	 * 支持+,-,*,/,+=,-=,/=,%,%=,pow,==,>=,<=,>,<,!=,流輸入,流輸出
	 * 請注意,沒有*=,原因自己想
	 * 要用的時候INT xxx就行了
	 *                                      2023.9.17       qmr工作室
	 */
	//定義結(jié)構(gòu)體
	struct INT:vector<int> {
		INT(int n=0){ //初始化為0
			push_back(n);//加入
			check();
		}
		INT& check(){ //處理進位
			while(!empty()&&!back())pop_back();
			if(empty())return *this;
			for(int i =1 ;i<size();++i){
				(*this)[i]+=(*this)[i-1]/10;
				(*this)[i-1]%=10;
			}
			//處理最高位
			while(back()>=10){
				push_back(back()/10);
				(*this)[size()-2]%=10;
			}
			return *this;
		}
	};
	//輸入輸出
	istream& operator>>(istream &is,INT &n){
		string s;
		is>>s;
		n.clear();//函數(shù)進位
		for(int i=s.size()-1;i>=0;--i)n.push_back(s[i]-'0');
		return is;
	}
	ostream& operator<<(ostream &os,const INT &n){
		if(n.empty())os<<0;
		for(int i=n.size()-1;i>=0;--i)os<<n[i];
		return os;
	}
	//比較
	bool operator!=(const INT &a,const INT &b){
		if(a.size()!=b.size())return 1;
		for(int i=a.size()-1;i>=0;--i)
			if(a[i]!=b[i])return 1;
		return 0;
	}
	bool operator==(const INT &a,const INT &b){
		return !(a!=b);
	}
	bool operator<(const INT &a,const INT &b){
		if(a.size()!=b.size())return a.size()<b.size();
		for(int i=a.size()-1;i>=0;--i)
			if(a[i]!=b[i])return a[i]<b[i];
		return 0;
	}
	bool operator>(const INT &a,const INT &b){
		return b<a;
	}
	bool operator<=(const INT &a,const INT &b){
		return !(a>b);
	}
	bool operator>=(const INT &a,const INT &b){
		return !(a<b);
	}
	INT& operator+=(INT &a,const INT &b){
		if(a.size()<b.size())a.resize(b.size());
		for(int i=0;i!=b.size();++i)a[i]+=b[i];
		return a.check();
	}
	INT operator+(INT a,const INT &b){
		return a+=b;
	}
	//減法，返回差的絕對值
	INT& operator-=(INT &a,INT b){
		if(a<b)swap(a,b);
		for(int i=0;i!=b.size();a[i]-=b[i],++i)
			if(a[i]<b[i]){
				int j=i+1;
				while(!a[j])++j;
				while(j>i){
					--a[j];
					a[--j]+=10;
				}
			}
		return a.check();
	}
	INT operator-(INT a,const INT &b){
		return a-=b;
	}
	INT operator*(const INT &a,const INT &b){
		INT n;
		n.assign(a.size()+b.size()-1,0);
		for(int i=0;i!=a.size();++i)
			for(int j=0;j!=b.size();++j)
				n[i+j]+=a[i]*b[j];
		return n.check();
	}
	INT& operator*=(INT &a,const INT &b){
		return a=a*b;
	}
	//帶余除法
	INT divmod(INT &a,const INT &b){
		INT ans;
		for(int t=a.size()-b.size();a>=b;--t){
			INT d;
			d.assign(t+1,0);//初始化全部為 0
			d.back()=1;		  //最后一位改成 1
			INT c=b*d;		  //其實就是c賦予b的值
			while(a>=c){
				a-=c;
				ans+=d;
			}
		}
		return ans;
	}
	INT operator/(INT a,const INT &b){
		return divmod(a,b);
	}
	INT& operator/=(INT &a,const INT &b){
		return a=a/b;
	}
	INT& operator%=(INT &a,const INT &b){
		divmod(a,b);
		return a;
	}
	INT operator%(INT a,const INT &b){
		return a%=b;
	}
}
using namespace big_number;

STL

string 比較

bool cmp(string a,string b){
	if(a.size()>b.size()){
		return 1;
	}else if(a.size()<b.size()){
		return 0;
	}else{
		for(int i=0;i<max(a.size(),b.size());i++){
			if(a[i]<b[i]){
				return 0;
			}else if(a[i]>b[i]){
				return 1;
			}
		}
	}
	return 1;//控制相等輸出
}

后綴表達式

T161786 例 8.3-4 后綴表達式

#include<bits/stdc++.h>
using namespace std;
stack<int> st;
void vo(char c){
	int b=st.top();st.pop();
	int a=st.top();st.pop();
	if(c=='+') st.push(a+b);
	if(c=='-') st.push(a-b);
	if(c=='*') st.push(a*b);
	if(c=='/') st.push(a/b);
}
int main(){
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='@') break;
		if(s[i]=='.') continue;
		if(s[i]>='0'&&s[i]<='9'){
			int j=i,num=0;
			while(s[j]>='0'&&s[j]<='9'){
				num=num*10+s[j]-'0';
				j++;
			}
			i=j-1;st.push(num);
		}else vo(s[i]);
	}
	cout<<st.top();
	return 0;
}

T162142 例 8.3-5 中綴轉(zhuǎn)后綴表達式

#include<bits/stdc++.h>
using namespace std;
stack<char> op;
string s;
int num=0,w=0,d[200];
int main(){
	cin>>s;
	d['-']=d['+']=1,d['*']=d['/']=2,d['^']=3;
	for(int i=0;i<s.size();i++){
		if(s[i]=='@') break;
		if(s[i]>='0'&&s[i]<='9'){//數(shù)字
			int j=i,nm=0;
			while(s[j]>='0'&&s[j]<='9'){
				nm=nm*10+s[j]-'0';
				j++;
			}
			i=j-1;cout<<nm<<' ';
		}else if(s[i]=='('){//前括號
			op.push('(');
		}else if(s[i]==')'){//后括號
			while(!op.empty()&&op.top()!='('){
				cout<<op.top()<<' ';
				op.pop();
			}
			if(!op.empty()) op.pop();
		}else{//運算符
			while(!op.empty()&&d[op.top()]>=d[s[i]]){
				cout<<op.top()<<' ';
				op.pop();
			}
			op.push(s[i]);
		}
	}
	while(!op.empty()){
		cout<<op.top()<<' ';
		op.pop();
	}
	return 0;
}

T161491 例 8.3-6 中綴表達式的計算

#include<bits/stdc++.h>
using namespace std;
int flag=1,d[2000]={0};
stack<int> st;//數(shù)字
stack<char> op;//運算符
void vo(){//計算
	char c;
	if(!op.empty()){c=op.top();op.pop();}
	if(st.size()>=2){
		int b=st.top();st.pop();
		int a=st.top();st.pop();
		if(c=='+') st.push(a+b);
		if(c=='-') st.push(a-b);
		if(c=='*') st.push(a*b);
		if(c=='/') st.push(a/b);
		if(c=='^') st.push(pow(a,b));
	}else{flag=0;}
}
int main(){
	string s;
	cin>>s;//輸入
	d['-']=d['+']=1,d['*']=d['/']=2,d['^']=3; //為運算級別做準備
	if(s[0]=='-') s="0"+s;//防止開頭為負數(shù)
	for(int i=0;i<s.size();i++){
		if(s[i]=='@') break;
		if(s[i]>='0'&&s[i]<='9'){//數(shù)字
			int j=i,nm=0;
			while(s[j]>='0'&&s[j]<='9'){
				nm=nm*10+s[j]-'0';
				j++;
			}
			i=j-1;st.push(nm);
		}else if(s[i]=='('){//前括號
			op.push('(');
		}else if(s[i]==')'){//后括號
			while(!op.empty()&&op.top()!='(') vo();
			if(!op.empty()) op.pop();
			else {
				cout<<"NO";
				return 0;
			}
		}else{//運算符
		while(!op.empty()&&d[op.top()]>=d[s[i]]){
				vo();
			}
			op.push(s[i]);
		}
	}
	while(!op.empty()) vo();//算剩下的
	if(flag==0) {//錯誤情況
		cout<<"NO";
		return 0;
	}
	if(!st.empty()) cout<<st.top();
	else cout<<"NO";
	return 0;
}

stack 表達式括號匹配

#include<bits/stdc++.h>
using namespace std;
int main(){
	
	char a;
	string st;
	stack<char> s;
	getline(cin,st);
	int t=0;
	for(int o=0;o<st.size();o++){
		a=st[o];
		if(a=='['||a=='{'||a=='('||a=='<') {
			s.push(a);
        }else if(a==']'||a==')'||a=='>'||a=='}'){
			if(s.empty()){
				cout<<"Wrong"<<endl;t=1;
				break;
			}else if(s.top() == '<' && a== '>') {
				s.pop();
			}else if(s.top()=='(' && a==')'){//
				s.pop();
				if((!s.empty())&&s.top()=='<'){
					cout<<"Wrong"<<endl;t=1;
					break;
				}
			}else if(s.top() == '[' && a== ']') {
				s.pop();
				if((!s.empty())&&(s.top()=='('||s.top()=='<')){
					cout<<"Wrong"<<endl;t=1;
					break;
				}
			}else if(s.top()=='{' && a=='}'){//
				s.pop();
				if((!s.empty())&&s.top()!='{'){
					cout<<"Wrong"<<endl;t=1;
					break;
				}
			}else{
				cout<<"Wrong"<<endl;t=1;
				break;
			}
		}
	}
	if(t==0){
		if(!s.empty()){
			cout<<"Wrong"<<endl;
		}else{
			cout<<"OK"<<endl;
		}
	}
	
	return 0;
}

排序

快速排序

void qsort(int a[],int l,int r){
	int i=l,j=r,flag=a[(l+r)/2];
	do{
		while(a[i]>flag) i++;
		while(a[j]<flag) j--;
		if(i<=j){
			swap(a[i++],a[j--]);
		}
	}while(i<=j);
	if(l<j) qsort(a,l,j);
	if(i<r) qsort(a,i,r);
}

歸并排序

void mergesort(int l,int r){
	if(l>=r) return ;
	int mid=l+r>>1;
	mergesort(l,mid);mergesort(mid+1,r);
	long long zi=l,yi=1+mid,k=l;
	while(zi<=mid && yi<=r){
		if(F[zi]<=F[yi]) {a[k++]=F[zi++];}
		else {a[k++]=F[yi++];}
	}
	while(zi<=mid) a[k++]=F[zi++];
	while(yi<=r) a[k++]=F[yi++];
	for(int i=l;i<=r;i++) F[i]=a[i];
}

二分搜索

二分靠左

int ask_l(int k){
	int r=1,l=n;
	while(r<l){
		int mid=(r+l)/2;
		if(a[mid]>=k) l=mid;
		else r=mid+1;
	} 
	if(a[r]==k) return r-1;
	return -1;
}

二分靠右

int ask_r(int k){
	int r=1,l=n;
	while(r<l){
		int mid=(r+l+1)/2;
		if(a[mid]>k) l=mid-1;
		else r=mid;
	} 
	if(a[r]==k) return r-1;
	return -1;
}

二分查找相關(guān)函數(shù)

若存在序 a {0,1,3,3,3,5,8};

1. binary_search(a+1,a+n+1,x)
查找單調(diào)序列中，在指定區(qū)域內(nèi)[1,n]是否存在目標值x。存在返回true，不存在返回false
例：int k=binary_search(a+1,a+7,3)；//k=1

2. lower_bound(a+1,a+n+1,x)
查找不降序列中，在指定區(qū)域內(nèi)[1,n]大于等于目標值x的第一個元素所在地址。(靠左查找)
例：int pos=lower_bound(a+1,a+7,3)-a;//元素位置在a+2，因此pos=2。

3. upper_bound(a+1,a+n+1,x)
查找不降序列中，在指定區(qū)域內(nèi)[1,n]大于目標值x的第一個元素所在地址。(靠右查找)
例：int pos=lower_bound(a+1,a+7,3)-a;//元素位置在a+5，因此pos=5。

圖論

唯一的閱讀體驗 (圖的四種搜索方法)

唯一的閱讀體驗 (最小生成樹)

唯一的閱讀體驗 (DAG 與拓撲排序)

搜索

唯一的閱讀體驗

其他的閱讀體驗

數(shù)學

唯一的閱讀體驗

數(shù)據(jù)結(jié)構(gòu)：

分塊

int n;
int a[N],sum[N],add[N];
int L[N],R[N],pos[N];
void build(){
	int len=sqrt(n);
	for(int i=1;i<=len;i++){
		L[i]=(i-1)*len+1;
		R[i]=i*len;
	}
	if(R[len]<n) len++,L[len]=R[len-1]+1,R[len]=n;
	for(int i=1;i<=len;i++){
		for(int j=L[i];j<=R[i];j++)
			sum[i]+=a[j],pos[j]=i;
	}
}
void change(int l,int r,int c){
	int x=pos[l],y=pos[r];
	if(x==y){
		for(int i=l;i<=r;i++)
			a[i]+=c;
		sum[x]+=(r-l+1)*c;
		return;
	}
	for(int i=l;i<=R[x];i++) a[i]+=c,sum[x]+=c;
	for(int i=L[y];i<=r;i++) a[i]+=c,sum[y]+=c;
	for(int i=x+1;i<=y-1;i++) add[i]+=c,sum[i]+=(R[i]-L[i]+1)*c;
}
int ask(int l,int r,int m){
	int x=pos[l],y=pos[r],ans=0;
	if(x==y){
		for(int i=l;i<=r;i++)
			ans=(ans+a[i]+add[x])%m;
		return ans;
	}
	for(int i=l;i<=R[x];i++) ans=(ans+a[i]+add[x])%m;
	for(int i=L[y];i<=r;i++) ans=(ans+a[i]+add[y])%m;
	for(int i=x+1;i<=y-1;i++) ans=(ans+sum[i])%m;
	return ans;
}

樹狀數(shù)組

struct tree{
	int c[N];
	void add(int x,int a){
		for(int i=x;i<N;i+=(i&-i)) c[i]+=a;
	}
	int ask(int x){
		int ans=0;
		for(int i=x;i;i-=(i&-i)) ans+=c[i];
		return ans;
	}
}BIT;

線段樹

普通線段樹

struct SegmentTree{
	int l,r;//左右端點
	ull sum;//區(qū)間和
	ull add;//區(qū)間懶標記
	#define lc p<<1
	#define rc p<<1|1
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define sum(x) t[x].sum
	#define add(x) t[x].add
}t[N*4];
void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	if(l==r) {sum(p)=a[l];return;}
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	sum(p)=sum(lc)+sum(rc);
}
void push_down(int p){
	if(add(p)==0) return;
	sum(lc)+=add(p)*(r(lc)-l(lc)+1);
	sum(rc)+=add(p)*(r(rc)-l(rc)+1);
	add(lc)+=add(p);
	add(rc)+=add(p);
	add(p)=0;
}
void change(int p,int l,int r,ull k){
	if(l<=l(p) && r>=r(p)) {sum(p)+=(r(p)-l(p)+1)*k;add(p)+=k;return;}
	push_down(p);
	int mid=l(p)+r(p)>>1;
	if(l<=mid) change(lc,l,r,k);
	if(r>mid) change(rc,l,r,k);
	sum(p)=sum(lc)+sum(rc);
}
ull ask(int p,int l,int r){
	if(l<=l(p) && r>=r(p)) {return sum(p);}
	push_down(p);
	ull ans=0;
	int mid=l(p)+r(p)>>1;
	if(l<=mid) ans+=ask(lc,l,r);
	if(r>mid) ans+=ask(rc,l,r);
	return ans;
}

動態(tài)開點線段樹

inline void change(int &p,int l,int r,int x,int k){
	if(!p) p=++cnt;
	sum[p]++;
	if(l==r){return;}
	int mid=l+r>>1;
	if(x<=mid) change(lc[p],l,mid,x,k);
	if(x>mid) change(rc[p],mid+1,r,x,k);
}
inline int ask(int &p,int l,int r,int x,int y){
	if(!p) return 0;
	if(x<=l&&r<=y) return sum[p];
	int mid=l+r>>1,ans=0;
	if(x<=mid) ans+=ask(lc[p],l,mid,x,y);
	if(y>mid) ans+=ask(rc[p],mid+1,r,x,y);
	return ans;
}

標記永久化：

inline void change(int &p,int l,int r,int x,int y,int k){
	if(!p) p=++cnt;
	if(x<=l&&r<=y){
		sum[p]+=k*(r-l+1);
		tag[p]+=k;
	    return;
	}
	sum[p]+=k*(min(r,y)-max(x,l)+1);
	int mid=l+r>>1;
	if(x<=mid) change(lc[p],l,mid,x,y,k);
	if(y>mid) change(rc[p],mid+1,r,x,y,k);
}
inline int ask(int &p,int l,int r,int x,int y,int val){
	if(!p) return val*(min(r,y)-max(x,l)+1);
	if(x<=l&&r<=y) return sum[p]+val*(r-l+1);
	int mid=l+r>>1,ans=0;
	if(x<=mid) ans+=ask(lc[p],l,mid,x,y,val+tag[p]);
	if(y>mid) ans+=ask(rc[p],mid+1,r,x,y,val+tag[p]);
	return ans;
}

線段樹合并：

void Merge(int &a,int b){
	if(!a||!b) {a=a+b;return;}
	sum[a]=sum[a]+sum[b];
	Merge(lc[a],lc[b]);
	Merge(rc[a],rc[b]);
}

線段樹分裂：

void split(int &a,int &b,int l,int r,int x,int y){
	if(!a) return;
	if(x<=l&&r<=y){
		b=a,a=0;
		return;
	}
	if(!b) b=++cnt;
	int mid=l+r>>1;
	if(x<=mid) split(lc[a],lc[b],l,mid,x,y);
	if(y>mid) split(rc[a],rc[b],mid+1,r,x,y);
	push_up(a),push_up(b);
}

可持久化：

struct node{
    int lc,rc,sum;
}t[N*42];
inline void build(int &p,int l,int r){
	p=++cnt;
	t[p].sum=0;
	if(l==r){return;}
	int mid=l+r>>1;
	build(t[p].lc,l,mid);
	build(t[p].rc,mid+1,r);
}
inline void change(int &a,int b,int l,int r,int x,int k){
	a=++cnt;
	if(l==r){t[a].sum=t[b].sum+k;return;}
	t[a].sum=t[b].sum+k,t[a].lc=t[b].lc,t[a].rc=t[b].rc;
	int mid=l+r>>1;
	if(x<=mid) change(t[a].lc,t[b].lc,l,mid,x,k);
	if(x>mid) change(t[a].rc,t[b].rc,mid+1,r,x,k);
}
inline int ask(int a,int b,int l,int r,int x){
	if(l==r) return l;
	int mid=l+r>>1;
	int s=t[t[b].lc].sum-t[t[a].lc].sum;
	if(s>=x) return ask(t[a].lc,t[b].lc,l,mid,x);
	else return ask(t[a].rc,t[b].rc,mid+1,r,x-s);
}

線段樹分治：

動態(tài)圖連通性

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
using namespace std;
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
const int N=5e3+5,M=5e5+5;
int n,m,top;
struct node{
	int op,x,y;
}opt[M],s[M];
int fa[M],h[M];
int lst[N][N];
vector<node> v[M<<2];
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
void change(int p,int l,int r,int x,int y,int a,int b){
	if(x<=l && r<=y){
		v[p].push_back({0,a,b});
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) change(lc,l,mid,x,y,a,b);
	if(y>mid) change(rc,mid+1,r,x,y,a,b);
}
void init(){
	for(int i=1;i<=m;i++){
		int op=opt[i].op,x=opt[i].x,y=opt[i].y;
		if(op==1) lst[x][y]=i;
		if(op==2) {
			change(1,1,m,lst[x][y],i-1,x,y);
			lst[x][y]=0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(lst[i][j]) change(1,1,m,lst[i][j],m,i,j);
		}
	}
}
int find(int x){
	if(x==fa[x]) return x;
	return find(fa[x]);
}
void Merge(int x,int y){//把y放在x
	int rx=find(x),ry=find(y);
	if(rx==ry) return;
	if(h[rx]<h[ry]) swap(rx,ry);
	s[++top]={h[rx],rx,ry};
	fa[ry]=rx,h[rx]+=(h[rx]==h[ry]);
}
void dfs(int p,int l,int r){
	int now=top;
	for(int i=0;i<v[p].size();i++){
		Merge(v[p][i].x,v[p][i].y);
	}
	int mid=l+r>>1;
	if(l==r){
		if(opt[l].op==3){
			if(find(opt[l].x)==find(opt[l].y)) puts("Y");
			else puts("N");
		}
	}else{
		dfs(lc,l,mid);
		dfs(rc,mid+1,r);
	}
	while(now<top){
		fa[s[top].y]=s[top].y;
		h[s[top].x]=s[top].op;
		top--;
	}
}
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int op,x,y;scanf("%d%d%d",&op,&x,&y);
		if(x>y) swap(x,y);
		opt[i]={op+1,x,y};
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	init();
	dfs(1,1,m);
	return 0;
}

二維線段樹

void changeY(int &s,int l,int r,int y,int a){
	if(!s) s=++cntY;
	t[s].sum+=a;
	if(l==r) return;
	int mid=l+r>>1;
	if(y<=mid) changeY(t[s].l,l,mid,y,a);
	else changeY(t[s].r,mid+1,r,y,a);
}
void changeX(int &p,int l,int r,int x,int y,int a){
	if(!p) p=++cntX;
	changeY(rt[p],1,n,y,a);
	if(l==r) return;
	int mid=l+r>>1;
	if(x<=mid) changeX(lc[p],l,mid,x,y,a);
	else changeX(rc[p],mid+1,r,x,y,a);
}
int askY(int s,int l,int r,int ay,int by){
	if(!s) return 0;
	if(ay<=l&&r<=by) return t[s].sum;
	int mid=l+r>>1,ans=0;
	if(ay<=mid) ans+=askY(t[s].l,l,mid,ay,by);
	if(by>mid) ans+=askY(t[s].r,mid+1,r,ay,by);
	return ans;
}
int askX(int p,int l,int r,int ax,int bx,int ay,int by){
	if(!p) return 0;
	if(ax<=l&&r<=bx) return askY(rt[p],1,n,ay,by);
	int mid=l+r>>1,ans=0;
	if(ax<=mid) ans+=askX(lc[p],l,mid,ax,bx,ay,by);
	if(bx>mid) ans+=askX(rc[p],mid+1,r,ax,bx,ay,by);
	return ans;
}

CDQ

struct node{//元素信息
	int a,b,c;
	int cnt,ans;
}e[N],a[N],tmp[N];
struct tree{
	int c[N];
	void add(int x,int a){
		for(int i=x;i<N;i+=(i&-i)) c[i]+=a;
	}
	int ask(int x){
		int ans=0;
		for(int i=x;i;i-=(i&-i)) ans+=c[i];
		return ans;
	}
}BIT;
bool operator != (node a,node b){
	return a.a!=b.a||a.b!=b.b||a.c!=b.c;
}
bool cmpA(node a,node b){
	if(a.a!=b.a) return a.a<b.a;
	if(a.b!=b.b) return a.b<b.b;
	return a.c<b.c;
}
bool cmpB(node a,node b){
	if(a.b!=b.b) return a.b<b.b;
	return a.c<b.c;
}
void CDQ(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	CDQ(l,mid),CDQ(mid+1,r);
	int i=l,j=mid+1,tot=l;
	while(j<=r&&i<=mid){
		if(a[i].b<=a[j].b) BIT.add(a[i].c,a[i].cnt),tmp[tot++]=a[i++];
		else a[j].ans+=BIT.ask(a[j].c),tmp[tot++]=a[j++];
	}
	while(i<=mid) BIT.add(a[i].c,a[i].cnt),tmp[tot++]=a[i++];
	while(j<=r) a[j].ans+=BIT.ask(a[j].c),tmp[tot++]=a[j++];
	for(int ii=l;ii<=mid;ii++) BIT.add(a[ii].c,-a[ii].cnt);
	for(int ii=l;ii<=r;ii++) a[ii]=tmp[ii];
}

二維 CDQ

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
const int N=1e5+5;
int n;//點的數(shù)量
int k;//去重后點的數(shù)量
int m;//離散化后d的數(shù)量
int h[N];//Hash
struct node{
	int a,b,c,d;//四個位置
	int w;//貢獻
	int ans;//答案
	int falg;//標記左邊，右邊
	int id;//原位置
	bool operator ==(const node &p) const{
		return a==p.a&&b==p.b&&c==p.c&&d==p.d;
	}
}u[N],tmp[N];
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
bool cmpA(node a,node b){
	if(a.a!=b.a) return a.a<b.a;
	if(a.b!=b.b) return a.b<b.b;
	if(a.c!=b.c) return a.c<b.c;
	return a.d<b.d;
}
bool cmpB(node a,node b){
	if(a.b!=b.b) return a.b<b.b;
	if(a.c!=b.c) return a.c<b.c;
	if(a.d!=b.d) return a.d<b.d;
	return a.a<b.a;
}
bool cmpC(node a,node b){
	if(a.c!=b.c) return a.c<b.c;
	if(a.d!=b.d) return a.d<b.d;
	if(a.a!=b.a) return a.a<b.a;
	return a.b<b.b;
}
struct tree{
	int c[N];
	void add(int x,int a){
		for(int i=x;i<=m;i+=(i&-i)) c[i]=max(c[i],a);
	}
	int ask(int x){
		int ans=0;
		for(int i=x;i;i-=(i&-i)) ans=max(ans,c[i]);
		return ans;
	}
	void clear(int x){
		for(int i=x;i<=m;i+=(i&-i)) c[i]=0;
	}
}BIT;
void CDQ2(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	CDQ2(l,mid),CDQ2(mid+1,r);
	int i=l,j=mid+1,tot=l;
	while(j<=r&&i<=mid){
		if(u[i].c<=u[j].c){
			if(u[i].falg==1) BIT.add(u[i].d,u[i].ans);
			tmp[tot++]=u[i++];
		}
		else{
			if(u[j].falg==0) u[j].ans=max(u[j].ans,BIT.ask(u[j].d)+u[j].w);
			tmp[tot++]=u[j++];
		}
	}
	while(i<=mid) {
		if(u[i].falg==1) BIT.add(u[i].d,u[i].ans);
		tmp[tot++]=u[i++];
	}
	while(j<=r) {
		if(u[j].falg==0) u[j].ans=max(u[j].ans,BIT.ask(u[j].d)+u[j].w);
		tmp[tot++]=u[j++];
	}
	for(i=l;i<=mid;i++) if(u[i].falg) BIT.clear(u[i].d);
	for(i=l;i<=r;i++) u[i]=tmp[i];
}
void CDQ1(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	CDQ1(l,mid);
	for(int i=l;i<=mid;i++) u[i].falg=1;
	for(int i=mid+1;i<=r;i++) u[i].falg=0;
	
	sort(u+l,u+r+1,cmpB);
	CDQ2(l,r);
	
	for(int i=l;i<=r;i++) tmp[u[i].id]=u[i];
	for(int i=l;i<=r;i++) u[i]=tmp[i];
	
	CDQ1(mid+1,r);
}
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>u[i].a>>u[i].b>>u[i].c>>u[i].d;
		h[i]=u[i].d,u[i].w=1;
	}
	sort(h+1,h+n+1);
	sort(u+1,u+n+1,cmpA);
	m=unique(h+1,h+n+1)-h-1;//Hash
	k=1;
	for(int i=2;i<=n;i++){
		if(u[i]==u[k]) u[k].w++;
		else u[++k]=u[i];
	}
	for(int i=1;i<=k;i++){
		u[i].id=i;
		u[i].ans=u[i].w;
		u[i].d=lower_bound(h+1,h+m+1,u[i].d)-h;
	}
	CDQ1(1,k);
	int ans=0;
	for(int i=1;i<=k;i++) ans=max(ans,u[i].ans);
	cout<<ans;
	return 0;
}

整體二分

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
const int N=2e5+5;
int n,m,tot;
int ans[N];
struct node{
	int op,x,y,k;
	int id;
}p[N<<1],ll[N<<1],rr[N<<1];
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
struct tree{
	int c[N];
	void add(int x,int a){
		for(int i=x;i<=n;i+=(i&-i)) c[i]+=a;
	}
	int ask(int x){
		int ans=0;
		for(int i=x;i;i-=(i&-i)) ans+=c[i];
		return ans;
	}
}BIT;
void solve(int l,int r,int al,int ar){
	if(l>r || al>ar) return;
	if(l==r){
		for(int i=al;i<=ar;i++)
		    if(p[i].op) ans[p[i].id]=l;
		return;
	}
	int mid=l+r>>1;//假設(shè)所有的第k小皆為mid
	int nl=0,nr=0;
	for(int i=al;i<=ar;i++){
		if(p[i].op==0){//修改
			if(p[i].y<=mid){//x<=mid
				BIT.add(p[i].x,1);
			    ll[++nl]=p[i];
			}else rr[++nr]=p[i];
		}else{//查詢
			int s=BIT.ask(p[i].y)-BIT.ask(p[i].x-1);
			if(s>=p[i].k) ll[++nl]=p[i];
			//在[l,r]的區(qū)間內(nèi)小于mid的個數(shù)大于等于k，相當于mid>=ans
			else p[i].k-=s,rr[++nr]=p[i];
			//在[l,r]的區(qū)間內(nèi)小于mid的個數(shù)小于k，相當于mid<ans
		}
	}
	for(int i=1;i<=nl;i++) p[al+i-1]=ll[i];
	for(int i=1;i<=nr;i++) p[al+nl+i-1]=rr[i];
	for(int i=al;i<=ar;i++)
		if(p[i].id==0&&p[i].y<=mid) BIT.add(p[i].x,-1);
	solve(l,mid,al,al+nl-1);
	solve(mid+1,r,al+nl,ar);
}
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
signed main(){
	ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		p[++tot]={0,i,x,0,0};
	}
	for(int i=1;i<=m;i++){
		int x,y,k;cin>>x>>y>>k;
		p[++tot]={1,x,y,k,i};
	}
	solve(1,1e9,1,tot);
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
	return 0;
}

平衡樹：

Splay：

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
const int N=1e5+5;
int n;//n
int root;//樹之根
int tot;//開點編號
struct node{
	int s[2];//左右兒子
	int fa;//父親
	int val;//節(jié)點數(shù)字
	int cnt;//重復個數(shù)
	int siz;//子樹大小
	#define ls T[p].s[0]
	#define rs T[p].s[1]
}T[N<<1];
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
void push_up(int p){
	T[p].siz=T[ls].siz+T[rs].siz+T[p].cnt;
}
inline void rotate(int x){
	int y=T[x].fa,z=T[y].fa;
	int k1=(T[y].s[1]==x);//k=0:x是y的左兒子 k=1:x是y的右兒子
	int k2=(T[z].s[1]==y);//k=0:y是z的左兒子 k=1:y是z的右兒子
	T[z].s[k2]=x,T[x].fa=z;
	T[y].s[k1]=T[x].s[k1^1];
	T[T[x].s[k1^1]].fa=y;
	T[x].s[k1^1]=y,T[y].fa=x;
	push_up(y),push_up(x);
}
inline void Splay(int x,int k){//原點；目標點
	while(T[x].fa!=k){
		int y=T[x].fa,z=T[y].fa;
		if(z!=k) //爸爸的爸爸不是k(爺爺)
			( (T[z].s[0]==y) ^ (T[y].s[0]==x) )?rotate(x):rotate(y);
		rotate(x);
	}
	if(!k) root=x;
}
inline void find(int x){//找到x點;并將其旋轉(zhuǎn)至root
	int p=root;
	while(T[p].s[(x>T[p].val)] && x!=T[p].val)
		p=T[p].s[(x>T[p].val)];
	Splay(p,0);
}
int get_pre(int x){
	find(x);
	int p=root;
	if(T[p].val<x) return p;
	p=ls;
	while(rs) p=rs;
	Splay(p,0);
	return p;
}
int get_suc(int x){
	find(x);
	int p=root;
	if(T[p].val>x) return p;
	p=rs;
	while(ls) p=ls;
	Splay(p,0);
	return p;
}
void ins(int x){
	int p=root,fa=0;
	while(p&&T[p].val!=x)
		fa=p,p=T[p].s[(T[p].val<x)];
	if(p) T[p].cnt++;
	else{
		p=++tot;
		T[fa].s[(T[fa].val<x)]=p;
		T[p]={{0,0},fa,x,1,1};
	}
	Splay(p,0);
}
void del(int x){
	int pre=get_pre(x);
	int suc=get_suc(x);
	Splay(pre,0);
	Splay(suc,pre);
	int p=T[suc].s[0];
	if(T[p].cnt>1){
		T[p].cnt--;
		Splay(p,0);
	}else{
		T[suc].s[0]=0;
		Splay(suc,0);
	}
}
int get_rank(int x){
	ins(x);
	int ans=T[T[root].s[0]].siz;
	del(x);
	return ans;
}
int get_val(int k){
	int p=root;
	while(true){
		if(T[ls].siz+T[p].cnt<k){
			k-=(T[ls].siz+T[p].cnt);
			p=rs;
		}else{
			if(T[ls].siz>=k) {
			    p=ls;
		    }else break;
		}
	}
	Splay(p,0);
	return T[p].val;
}
inline int read(){
	int s=0,f=1; char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}
	return s*f;
}
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
int main() {
	n=read();
	ins(2147483647);
	ins(-2147483648);
	while(n--) {
		int opt=read(),x=read();
		if(opt==1) ins(x);
		if(opt==2) del(x);
		if(opt==3) printf("%d\n",get_rank(x));
		if(opt==4) printf("%d\n",get_val(x+1));
		if(opt==5) printf("%d\n",T[get_pre(x)].val);
		if(opt==6) printf("%d\n",T[get_suc(x)].val);
	}
    return 0;
}

Head Treap

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,tot,root;
struct node{
	int s[2];
	int val,siz;//點的編號;子樹中cnt之和
	int cnt,rnd;//當前節(jié)點的重疊數(shù);隨即優(yōu)先級
	#define ls T[p].s[0]
	#define rs T[p].s[1]
}T[N<<1];
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
void push_up(int p){
	T[p].siz=T[ls].siz+T[rs].siz+T[p].cnt;
}
int new_node(int x){
	T[++tot]={{0,0},x,1,1,rand()};
	return tot;
}
void rotate(int &p,int d){//左旋為0,右旋為1
	int k=T[p].s[d^1];
	T[p].s[d^1]=T[k].s[d];
	T[k].s[d]=p;
	push_up(p),push_up(k);
	p=k;
}
void ins(int &p,int x){
	if(!p){
		p=new_node(x);
		return;
	}
	if(T[p].val==x){
		T[p].cnt++;
		T[p].siz++;
		return;
	}
	int d=x>T[p].val;
	ins(T[p].s[d],x);
	if(T[p].rnd<T[T[p].s[d]].rnd) rotate(p,d^1);
	push_up(p);
}
void del(int &p,int x){
	if(!p) return;
	if(x<T[p].val) del(ls,x);
	else if(x>T[p].val) del(rs,x);
	else{
		if(!ls && !rs){
			T[p].cnt--,T[p].siz--;
			if(T[p].cnt==0) p=0;
		}else if(ls && !rs){
			rotate(p,1);
			del(rs,x);
		}else if(!ls && rs){
            rotate(p,0);
			del(ls,x);
		}else{
			bool d=(T[ls].rnd>T[rs].rnd);
			rotate(p,d);
			del(T[p].s[d],x);
		}
	}
	push_up(p);
}
int ask(int p,int x){
	if(!p)return 0;
	if(T[p].val==x)return T[ls].siz;
	if(T[p].val>x)return ask(ls,x);
	return ask(rs,x)+T[ls].siz+T[p].cnt;
}
int kth(int p,int x){
	if(!p) return 0;
	int ans=T[ls].siz;
	if(ans>=x) return kth(ls,x);
	else if(ans+T[p].cnt>=x) return T[p].val;
	else return kth(rs,x-ans-T[p].cnt);
}
inline int read(){
	int s=0,f=1; char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}
	return s*f;
}
int main() {
	srand(time(0));
	n=read();
	while(n--) {
		int opt=read(),x=read();
		if(opt==1) ins(root,x);
		if(opt==2) del(root,x);
		if(opt==3) printf("%d\n",ask(root,x)+1);
		if(opt==4) printf("%d\n",kth(root,x));
		if(opt==5) printf("%d\n",kth(root,ask(root,x)));
		if(opt==6) printf("%d\n",kth(root,ask(root,x+1)+1));
	}
    return 0;
}

FHQ-Treap

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
const int N=1e5+5;
int n;
int root,cnt;
struct node{
	int lc,rc;
	int val,siz,rnd;
	#define ls T[p].lc
	#define rs T[p].rc
}T[20*N];
/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
void print(int x){
	if(!x) return;
	print(T[x].lc);
	cout<<T[x].val<<" ";
	print(T[x].rc);
}
void printt(int x){
	cout<<"Case: "<<x<<":\n";
	print(x);
	cout<<"\n\n";
}
void push_up(int p){
	T[p].siz=T[ls].siz+T[rs].siz+1;
}
int new_node(int x){
	T[++cnt]={0,0,x,1,rand()};
	return cnt;
}
void spilt_val(int p,int k,int &x,int &y){//按值分裂
	if(!p) {x=y=0;return;}
	if(T[p].val<=k) x=p,spilt_val(rs,k,T[x].rc,y);
	else y=p,spilt_val(ls,k,x,T[y].lc);
	push_up(p);
}
void spilt_siz(int p,int k,int &x,int &y){//按大小分裂
	if(!p) {x=y=0;return;}
	if(T[p].siz<=k) x=p,spilt_siz(ls,k,T[x].rc,y);
	else y=p,spilt_siz(rs,k,x,T[y].lc);
	push_up(p);
}
int Merge(int x,int y){//返回值為新樹的根
	if(!x||!y) return max(x,y);
	if(T[x].rnd<T[y].rnd){
		T[x].rc=Merge(T[x].rc,y);
        push_up(x);
		return x;
	}else{
		T[y].lc=Merge(x,T[y].lc);
		push_up(y);
		return y;
	}
}
void ins(int a){//加入元素a
	int x=0,y=0;//左,右
	spilt_val(root,a,x,y);
//	printt(x),printt(y);
	root=Merge(Merge(x,new_node(a)),y);
}
void del(int a){
	int x,y,z;
	spilt_val(root,a,x,z);
	spilt_val(x,a-1,x,y);
	y=Merge(T[y].lc,T[y].rc);
	root=Merge(Merge(x,y),z);
}
int ask(int a){
	int x,y;
	spilt_val(root,a-1,x,y);
	int ans=T[x].siz+1;
	root=Merge(x,y);
	return ans-1;
}
int kth(int p,int x){
	if(!p) return 0;
	int ans=T[ls].siz;
	if(ans>=x) return kth(ls,x);
	else if(ans+1>=x) return T[p].val;
	else return kth(rs,x-ans-1);
}
inline int read(){
	int s=0,f=1; char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}
	return s*f;
}

/*!@#$%^&*!@#$%^&*~~優(yōu)美的分界線~~*&^%$#@!*&^%$#@!*/
signed main(){
	srand(time(0));
	n=read();
	ins(INT_MAX);
	ins(INT_MIN);
	while(n--) {
		int opt=read(),x=read();
		if(opt==1) ins(x);
		if(opt==2) del(x);
		if(opt==3) printf("%d\n",ask(x));
		if(opt==4) printf("%d\n",kth(root,x+1));
		if(opt==5) {
			int l,r;
			spilt_val(root,x-1,l,r);
			cout<<kth(l,T[l].siz)<<'\n';
			root=Merge(l,r);
		}
		if(opt==6) {
			int l,r;
			spilt_val(root,x,l,r);
			cout<<kth(r,1)<<'\n';
			root=Merge(l,r);
		}
	}
	return 0;
}

替罪羊

#include<bits/stdc++.h>
using namespace std;
int n,tot,root; 
const int N=1e5+5;
const double alpha=0.75;
inline int read(){
	int s=0,f=1; char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}
	return s*f;
}
struct node{
	#define ls tr[p].lc
	#define rs tr[p].rc 
	int lc,rc;
	int val,sz,cnt;//sz子樹中數(shù)的個數(shù)
	int sn,tn;//sn總的節(jié)點個數(shù),tn實際的節(jié)點個數(shù)
}tr[N<<1];
int tmp[N],tmp_n;//臨時數(shù)組，用來儲存不平衡的子樹
void pushup(int p){//向上更新節(jié)點信息 
	tr[p].sz=tr[ls].sz+tr[rs].sz+tr[p].cnt;
	tr[p].sn=tr[ls].sn+tr[rs].sn+1;
	tr[p].tn=tr[ls].tn+tr[rs].tn+(tr[p].cnt?1:0);
}
int get_node(int x){//創(chuàng)建一個值為x的新節(jié)點 
	++tot;
	tr[tot]={0,0,x,1,1,1,1};
	return tot;
}
bool check(int p){//判斷是否平衡 
	if(tr[ls].sn>tr[p].sn*alpha||tr[rs].sn>tr[p].sn*alpha) return 0;//若左右子樹節(jié)點差的太多 
	if(tr[p].tn<tr[p].sn*alpha) return 0;//若已經(jīng)被刪除的節(jié)點太多 
	return 1;
}
//將子樹壓扁為數(shù)列
void flatt(int p){
	if(!p) return;
	flatt(ls);
	if(tr[p].cnt>0) tmp[++tmp_n]=p;//若該節(jié)點沒被刪出，將標號壓入臨時數(shù)組 
	flatt(rs);
} 
//將數(shù)列重新變?yōu)槠胶獾臉?int build(int l,int r){
	if(l>r) return 0;
	int mid=l+r>>1;
	int p=tmp[mid];//將存儲在數(shù)組中的標號取出 
	ls=build(l,mid-1);
	rs=build(mid+1,r);
	pushup(p);
	return p;
} 
//統(tǒng)一調(diào)用進行重建操作,注意要取址，因為要更改原節(jié)點的左右兒子關(guān)系 
void rebuild(int &p){
	tmp_n=0;
	flatt(p);
	if(p) p=build(1,tmp_n);
	else p=0;
} 
void ins(int &p,int x){
	if(!p){
		p=get_node(x);
		return;
	}
	if(tr[p].val>x) ins(tr[p].lc,x);
	else if(tr[p].val<x) ins(tr[p].rc,x);
	else tr[p].cnt++;
	pushup(p);
	if(!check(p)) rebuild(p);//若不平衡，則重構(gòu)子樹 
}
void del(int &p,int x){
	if(!p) return;
	if(tr[p].val>x) del(ls,x);
	else if(tr[p].val<x) del(rs,x);
	else tr[p].cnt--;
	pushup(p);
	if(!check(p)) rebuild(p);
}
int ask(int p,int x){
	if(!p)return 0;
	if(tr[p].val==x)return tr[ls].sz;
	if(tr[p].val>x)return ask(ls,x);
	return ask(rs,x)+tr[ls].sz+tr[p].cnt;
}
int kth(int p,int x){
	if(!p) return 0;
	int ans=tr[tr[p].lc].sz;
	if(ans>=x) return kth(ls,x); 
	else if(ans+tr[p].cnt>=x) return tr[p].val;
	else return kth(rs,x-ans-tr[p].cnt); 
}
int main() {
	n=read();
	ins(root,INT_MAX);
	ins(root,INT_MIN);
	while(n--){
		int opt=read(),x=read();
		if(opt==1) ins(root,x);
		if(opt==2) del(root,x);
		if(opt==3) printf("%d\n",ask(root,x));
		if(opt==4) printf("%d\n",kth(root,x+1));
		if(opt==5) printf("%d\n",kth(root,ask(root,x)));
		if(opt==6) printf("%d\n",kth(root,ask(root,x+1)+1)); 
	}
    return 0;
}