模板大全
基础
进制转化
N进制转十进制：
long long binary1(string s,int n){//s为输入N进制，n为进制数。
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;
}十进制转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;
}质数判断
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;
}回文数判断
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工作室
*/
//定义结构体
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();//函数进位
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 中缀转后缀表达式
#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'){//数字
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;//数字
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;//防止开头为负数
for(int i=0;i<s.size();i++){
if(s[i]=='@') break;
if(s[i]>='0'&&s[i]<='9'){//数字
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;
}二分查找相关函数 若存在序 a{0,1,3,3,3,5,8};
1. binary_search(a+1,a+n+1,x)
查找单调序列中，在指定区域内[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)
查找不降序列中，在指定区域内[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)
查找不降序列中，在指定区域内[1,n]大于目标值x的第一个元素所在地址。(靠右查找)
例：int pos=lower_bound(a+1,a+7,3)-a;//元素位置在a+5，因此pos=5。图论
唯一的阅读体验 (图的四种搜索方法)
唯一的阅读体验 (最小生成树)
唯一的阅读体验 (DAG与拓扑排序)
搜索
唯一的阅读体验
数学
唯一的阅读体验
数据结构
更好的阅读体验
数据结构：
分块
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;
}树状数组
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;//区间和
ull add;//区间懒标记
#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;
}动态开点
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);
}线段树分治：
动态图连通性
#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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--;
}
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=1e5+5;
int n;//点的数量
int k;//去重后点的数量
int m;//离散化后d的数量
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];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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);
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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;//假设所有的第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]的区间内小于mid的个数大于等于k，相当于mid>=ans
else p[i].k-=s,rr[++nr]=p[i];
//在[l,r]的区间内小于mid的个数小于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);
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=1e5+5;
int n;//n
int root;//树之根
int tot;//开点编号
struct node{
int s[2];//左右儿子
int fa;//父亲
int val;//节点数字
int cnt;//重复个数
int siz;//子树大小
#define ls T[p].s[0]
#define rs T[p].s[1]
}T[N<<1];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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点;并将其旋转至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;
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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;//当前节点的重叠数;随即优先级
#define ls T[p].s[0]
#define rs T[p].s[1]
}T[N<<1];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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;
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
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子树中数的个数
int sn,tn;//sn总的节点个数,tn实际的节点个数
}tr[N<<1];
int tmp[N],tmp_n;//临时数组，用来储存不平衡的子树
void pushup(int p){//向上更新节点信息
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){//创建一个值为x的新节点
++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;//若左右子树节点差的太多
if(tr[p].tn<tr[p].sn*alpha) return 0;//若已经被删除的节点太多
return 1;
}
//将子树压扁为数列
void flatt(int p){
if(!p) return;
flatt(ls);
if(tr[p].cnt>0) tmp[++tmp_n]=p;//若该节点没被删出，将标号压入临时数组
flatt(rs);
}
//将数列重新变为平衡的树
int build(int l,int r){
if(l>r) return 0;
int mid=l+r>>1;
int p=tmp[mid];//将存储在数组中的标号取出
ls=build(l,mid-1);
rs=build(mid+1,r);
pushup(p);
return p;
}
//统一调用进行重建操作,注意要取址，因为要更改原节点的左右儿子关系
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);//若不平衡，则重构子树
}
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;
}ค้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎้้้้้้้้๎๎๎้้้้้้้้๎๎