专栏文章

代码模板

UUnionRE
科技·工程参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miovxadh
此快照首次捕获于
2025/12/03 02:01
3 个月前
此快照最后确认于
2025/12/03 02:01
3 个月前
查看原文

Codes

代码模板

CPP
//#pragma GCC optimize("Ofast,no-stack-protector")
//#define _CRT_SECURE_NO_WARNINGS
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-falign-jumps")
//#pragma GCC optimize("-falign-loops")
//#pragma GCC optimize("-falign-labels")
//#pragma GCC optimize("-fdevirtualize")
//#pragma GCC optimize("-fcaller-saves")
//#pragma GCC optimize("-fcrossjumping")
//#pragma GCC optimize("-fthread-jumps")
//#pragma GCC optimize("-funroll-loops")
//#pragma GCC optimize("-fwhole-program")
//#pragma GCC optimize("-freorder-blocks")
//#pragma GCC optimize("-fschedule-insns")
//#pragma GCC optimize("inline-functions")
//#pragma GCC optimize("-ftree-tail-merge")
//#pragma GCC optimize("-fschedule-insns2")
//#pragma GCC optimize("-fstrict-aliasing")
//#pragma GCC optimize("-fstrict-overflow")
//#pragma GCC optimize("-falign-functions")
//#pragma GCC optimize("-fcse-skip-blocks")
//#pragma GCC optimize("-fcse-follow-jumps")
//#pragma GCC optimize("-fsched-interblock")
//#pragma GCC optimize("-fpartial-inlining")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("-freorder-functions")
//#pragma GCC optimize("-findirect-inlining")
//#pragma GCC optimize("-fhoist-adjacent-loads")
//#pragma GCC optimize("-frerun-cse-after-loop")
//#pragma GCC optimize("inline-small-functions")
//#pragma GCC optimize("-finline-small-functions")
//#pragma GCC optimize("-ftree-switch-conversion")
//#pragma GCC optimize("-foptimize-sibling-calls")
//#pragma GCC optimize("-fexpensive-optimizations")
//#pragma GCC optimize("-funsafe-loop-optimizations")
//#pragma GCC optimize("inline-functions-called-once")
//#pragma GCC optimize("-fdelete-null-pointer-checks")

//include:

#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>//用tree
// #include<ext/pb_ds/hash_policy.hpp>//用hash
// #include<ext/pb_ds/trie_policy.hpp>//用trie
// #include<ext/pb_ds/priority_queue.hpp>//用priority_queue

// using namespace __gnu_pbds;
// __gnu_pbds::priority_queue<T, Compare, Tag, Allocator>
// __gnu_pbds::tree<Key, Mapped, Cmp_Fn = std::less<Key>, Tag = rb_tree_tag,
//                  Node_Update = null_tree_node_update,
//                  Allocator = std::allocator<char>>

#define mp make_pair
#define cchash cc_hash_table<int,bool> 
#define gphash gp_hash_table<int,bool> 
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> bbtr;//平衡树
//tree不可重！！！

//存储的类型:long long
//映射类型:null_type,无映射(低版本g++为null_mapped_type)
//顺序:less<long long>,从小到大排序
//rb_tree_tag,红黑树
//更新方式 :tree_order_statistics_node_update,更新节点的顺序统计信息
#define pqueue __gnu_pbds::priority_queue
#define grt greater//greater<int>小根堆
#define pair_h pairing_heap_tag
#define thin_h thin_heap_tag
#define bino_h binomial_heap_tag 
#define rcbino_h rc_binomial_heap_tag
#define binary_h binary_heap_tag
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> tr;
/*
pairing_heap_tag
thin_heap_tag
binomial_heap_tag
rc_binomial_heap_tag 
binary_heap_tag
*/

//#define endl '\n'
#define pow fastpow
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
//unlocked WINDOWS会报错

inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}
	return x*f;
}//快读
inline void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}//快输
//常数较小的快输：
inline void fastwrite(int x) {
	static int sta[35];
	int top =0;
	do{sta[top++]=x%10,x/=10;}while (x);
	while(top) putchar(sta[--top]+48);
}
struct cnt_trie{
	vector<vector<int>>ch;
	vector<int>cnt;
	int ct=0;
	int gn_map[128];
	//如果用全局数组，不用vector，常数约为1/2
	void clear(){
		ch.clear();
		cnt.clear();
		ch.push_back(vector<int>(65, 0)); // 初始化根节点
		cnt.push_back(0);
		ct=0;
	}
	cnt_trie(){cnt_trie::init_gn();clear();}
    void init_gn() {
        for(int i=0;i<128;i++) gn_map[i]=-1;
        for(char c='A';c<='Z';c++) gn_map[c]=c-'A';
        for(char c='a';c<='z';c++) gn_map[c]=c-'a'+26;
        for(char c='0';c<='9';c++) gn_map[c]=c-'0'+52;
    }
	inline int gn(char x){return gn_map[(int)x];}
	void insert(string str){
		int p=0,l=str.size();
		for(int i=0;i<l;i++){
			int c=gn(str[i]);
			if(!ch[p][c]){
				ch.push_back(vector<int>(65, 0));//全局数组就不用这两个push_back，直接用
				cnt.push_back(0);
				ch[p][c]=++ct;
			}
			p=ch[p][c];
			cnt[p]++;
		}
	}
	int find_cnt(string str){
		int p=0,l=str.size();
		for(int i=0;i<l;i++){
			int c=gn(str[i]);
			if(!ch[p][c]) return 0;
			p=ch[p][c];
		}
		return cnt[p];
	}
	pair<int,int> find_range(string str){
		int p=0,l=str.size();
		for(int i=0;i<l;i++){
			int c=gn(str[i]);
			if(!ch[p][c]) return {0,0};
			p=ch[p][c];
		}
		return {p,ct};
	}
};
namespace fast_io{
	const int fread_cnt=(1<<20);
	const int fwrite_cnt=(1<<20);
	class fast_read{
	private:
		char buf_in[fread_cnt],*p1,*p2;
		inline char gc(){return (p1==p2&&(p2=(p1=buf_in)+fread(buf_in,1,fread_cnt,stdin),p1==p2)?EOF:*p1++);}
		inline bool read_bool(){char ch=gc();while(ch<'0'||ch>'1'){ch=gc();}return (ch=='1');}
		inline char read_ch(){char ch=gc();while(ch==' '||ch=='\r'||ch=='\n'||ch=='\t'){ch=gc();}return ch;}
		inline string read_string(){
			string s;char ch=gc();while(ch==' '||ch=='\r'||ch=='\n'||ch=='\t'){ch=gc();}
			while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!='\t'){s+=ch;ch=gc();}return s;
		}
		template <typename T>
		inline T read_int(){
			T x=0,f=1;char ch=gc();
			while(ch<'0'||ch>'9'){f=(ch=='-')?-f:f;ch=gc();}
			while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
			return x*f;
		}
		template <typename T>
		inline T read_unsigned(){
			T x=0;char ch=gc();while(ch<'0'||ch>'9'){ch=gc();}
			while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
			return x;
		}
		template <typename T>
		inline T read_float(){
			T x=0,f=1,c=1;char ch=gc();
			while(ch<'0'||ch>'9'){f=(ch=='-')?-f:f;ch=gc();}
			while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=gc();}
			if(ch=='.'){ch=gc();while(ch>='0'&&ch<='9'){c/=10;x+=c*(ch^48);ch=gc();}}
			return x*f;
		}
	public:
		fast_read& operator >> (bool &valx){valx=read_bool();return *this;}
		fast_read& operator >> (char &valx){valx=read_ch();return *this;}
		fast_read& operator >> (string &valx){valx=read_string();return *this;}
		fast_read& operator >> (float &valx){valx=read_float<float>();return *this;}
		fast_read& operator >> (double &valx){valx=read_float<double>();return *this;}
		fast_read& operator >> (long double &valx){valx=read_float<long double>();return *this;}
		fast_read& operator >> (short &valx){valx=read_int<short>();return *this;}
		fast_read& operator >> (int &valx){valx=read_int<int>();return *this;}
		fast_read& operator >> (long &valx){valx=read_int<long>();return *this;}
		fast_read& operator >> (long long &valx){valx=read_int<long long>();return *this;}
		fast_read& operator >> (unsigned short &valx){valx=read_unsigned<unsigned short>();return *this;}
		fast_read& operator >> (unsigned int &valx){valx=read_unsigned<unsigned int>();return *this;}
		fast_read& operator >> (unsigned long &valx){valx=read_unsigned<unsigned long>();return *this;}
		fast_read& operator >> (unsigned long long &valx){valx=read_unsigned<unsigned long long>();return *this;}
	}fin;
	class fast_write{
	private:
		char buf_out[fwrite_cnt],*p=buf_out;
		inline void write_bool(bool x){char ch=(x==1)?'1':'0';pc(ch);}
		inline void write_ch(char x){char ch=x;pc(ch);}
		inline void write_string(string s){for(string::iterator it=s.begin();it!=s.end();it=next(it)){pc(*it);}}
		template <typename T>
		inline void write_int(T x){
			if(x<(T)0){pc('-');x=-x;}
			if(x>=10){write_int(x/10);}pc((x%10)^48);
		}
		template <typename T>
		inline void write_unsigned(T x){
			if(x>=10){write_unsigned(x/10);}pc((x%10)^48);
		}
		template <typename T>
		inline void write_float(T x){
			if(x<(T)0)pc('-'),x=-x;
			write_int((int)x);pc('.');x-=(int)x;
			while(x!=0){x*=10;pc((int)x^48);x-=(int)x;}
		}
	public:
		inline void pc(char ch){if(p-buf_out==fwrite_cnt){fwrite(buf_out,1,fwrite_cnt,stdout),p=buf_out;}*p=ch;++p;}
		inline void flush(){fwrite(buf_out,1,p-buf_out,stdout);p=buf_out;}
		inline fast_write& operator << (bool valx){write_bool(valx);return *this;}
		inline fast_write& operator << (char valx){write_ch(valx);return *this;}
		inline fast_write& operator << (string valx){write_string(valx);return *this;}
		inline fast_write& operator << (float valx){write_float<float>(valx);return *this;}
		inline fast_write& operator << (double valx){write_float<double>(valx);return *this;}
		inline fast_write& operator << (long double valx){write_float<long double>(valx);return *this;}
		inline fast_write& operator << (short valx){write_int<short>(valx);return *this;}
		inline fast_write& operator << (int valx){write_int<int>(valx);return *this;}
		inline fast_write& operator << (long valx){write_int<long>(valx);return *this;}
		inline fast_write& operator << (long long valx){write_int<long long>(valx);return *this;}
		inline fast_write& operator << (unsigned short valx){write_unsigned<unsigned short>(valx);return *this;}
		inline fast_write& operator << (unsigned int valx){write_unsigned<unsigned int>(valx);return *this;}
		inline fast_write& operator << (unsigned long valx){write_unsigned<unsigned long>(valx);return *this;}
		inline fast_write& operator << (unsigned long long valx){write_unsigned<unsigned long long>(valx);return *this;}
		inline fast_write& operator << (fast_write& (*func)(fast_write&)){return func(*this);}
	}fout;inline fast_write& endl(fast_write& fastout){fastout.pc('\n');fastout.flush();return fastout;}
}using namespace fast_io;
#define int long long
int Reverse_order_pairs=0;//逆序对，个数
const int MAXN=1000001;
int a[MAXN],c[MAXN];
class Graph {//DAG有向无环图
private:
	int n;
	vector<unordered_map<int, int>> adj; // 邻接表，adj[u][v] = 初始边权w0
	vector<int> add_in;   // 每个节点的入边附加权值
	vector<int> add_out;  // 每个节点的出边附加权值
	vector<int> topo;     // 拓扑序
	vector<int> topo_index; // 节点在拓扑序中的索引
	vector<int> in_degree;  // 节点的入度
public:
	Graph(int num_nodes) : n(num_nodes), adj(num_nodes), add_in(num_nodes, 0), 
	add_out(num_nodes, 0), topo_index(num_nodes, -1), 
	in_degree(num_nodes, 0) {}
	
	// 添加有向边 u->v，初始权值为w
	void addedge(int u, int v, int w) {
		if (u < 0 || u >= n || v < 0 || v >= n) return;
		if (adj[u].find(v) == adj[u].end()) {
			adj[u][v] = w;
			in_degree[v]++;
		} else {
			adj[u][v] = w; // 如果边已存在，覆盖权值
		}
	}
	// 构建拓扑序
	void build_topo() {
		topo.clear();
		vector<int> in_deg = in_degree; // 复制入度数组
		queue<int> q;
		for (int i = 0; i < n; i++) {
			if (in_deg[i] == 0) {
				q.push(i);
			}
		}
		while (!q.empty()) {
			int u = q.front(); q.pop();
			topo.push_back(u);
			for (auto& edge : adj[u]) {
				int v = edge.first;
				if (--in_deg[v] == 0) {
					q.push(v);
				}
			}
		}
		// 设置拓扑序索引
		for (int i = 0; i < topo.size(); i++) {
			topo_index[topo[i]] = i;
		}
	}
	// 修改单边(u->v)的初始权值，加上delta
	void change_edge(int u, int v, int delta) {
		if (u < 0 || u >= n || v < 0 || v >= n) return;
		if (adj[u].find(v) != adj[u].end()) {
			adj[u][v] += delta;
		}
	}
	// 修改节点v的所有入边，每条边加上delta
	void change_in_edges(int v, int delta) {
		if (v >= 0 && v < n) {
			add_in[v] += delta;
		}
	}
	// 修改节点u的所有出边，每条边加上delta
	void change_out_edges(int u, int delta) {
		if (u >= 0 && u < n) {
			add_out[u] += delta;
		}
	}
	// 查询s到t的最短路径长度
	int shortest_path(int s, int t) {
		if (s < 0 || s >= n || t < 0 || t >= n) return INT_MIN;
		if (topo.empty() || topo_index[s] == -1) return INT_MIN;
		vector<long long> dist(n, LLONG_MAX / 2); // 防止溢出
		dist[s] = 0;
		int start_idx = topo_index[s];
		for (int i = start_idx; i < topo.size(); i++) {
			int u = topo[i];
			if (dist[u] == LLONG_MAX / 2) continue; // 不可达节点
			for (auto& edge : adj[u]) {
				int v = edge.first;
				int w0 = edge.second;
				long long actual_weight = (long long)w0 + add_out[u] + add_in[v];
				if (dist[u] + actual_weight < dist[v]) {
					dist[v] = dist[u] + actual_weight;
				}
			}
		}
		return (dist[t] >= LLONG_MAX / 2) ? INT_MIN : (int)dist[t];
	}
	// 查询s到t的最长路径长度
	int longest_path(int s, int t) {
		if (s < 0 || s >= n || t < 0 || t >= n) return INT_MIN;
		if (topo.empty() || topo_index[s] == -1) return INT_MIN;
		vector<long long> dist(n, LLONG_MIN);
		dist[s] = 0;
		int start_idx = topo_index[s];
		for (int i = start_idx; i < topo.size(); i++) {
			int u = topo[i];
			if (dist[u] == LLONG_MIN) continue; // 不可达节点
			for (auto& edge : adj[u]) {
				int v = edge.first;
				int w0 = edge.second;
				long long actual_weight = (long long)w0 + add_out[u] + add_in[v];
				if (dist[u] + actual_weight > dist[v]) {
					dist[v] = dist[u] + actual_weight;
				}
			}
		}
		return (dist[t] == LLONG_MIN) ? INT_MIN : (int)dist[t];
	}
};
const long long maxPrime=6000010,maxNumber=10000100;
bitset<maxNumber> isPrime;
int Prime[maxPrime];//质数
int cntPrime=0;
void GetPrime(int n){
	isPrime.set();
	isPrime[1]=0;
	for(int i=2;i<=n;i++){
		if(isPrime[i])Prime[++cntPrime]=i; 
		for(int j=1;j<=cntPrime&&i*Prime[j]<=n;j++) {
			isPrime[i*Prime[j]]=0;
			if(i%Prime[j]==0)break; 
		}
	}
}
//支持对a数组排序
void MergeSort(int beg,int end)//begin&end
{
	if(beg==end)  
		return;
	int mid=(beg+end)/2,i=beg,j=mid+1,k=beg;
	MergeSort(beg,mid),MergeSort(mid+1,end);
	while(i<=mid&&j<=end)
		if(a[i]<=a[j])
			
			c[k++]=a[i++];
	else{
		c[k++]=a[j++];
		Reverse_order_pairs+=mid-i+1;//左边即个数
	}//inplace_merge();
	
	while(i<=mid)c[k++]=a[i++];
	while(j<=end)c[k++]=a[j++];
	for(int x=beg;x<=end;x++)a[x]=c[x];
} //归并排序

namespace largetype{
	class largeint{
	private:
		string num;
		bool isNegative;
	public:
		largeint():num("0"),isNegative(false){}
		largeint(const string& s){
			if(s.empty()){
				num="0";
				isNegative=false;
				return;
			}
			isNegative=(s[0]=='-');
			num=isNegative?s.substr(1):s;
		}
		largeint(int n){
			if(n==0){
				num="0";
				isNegative=false;
				return;
			}
			isNegative=(n<0);
			num=to_string(abs(n));
		}
		string getNum()const{return num;}
		bool getIsNegative()const{return isNegative;}
		bool operator<(const largeint& other)const{
			if(isNegative!=other.isNegative)return isNegative;
			if(num.length()!=other.num.length())
				return isNegative?(num.length()>other.num.length()):(num.length()<other.num.length());
			return isNegative?(num>other.num):(num<other.num);
		}
		bool operator==(const largeint& other)const{return num==other.num&&isNegative==other.isNegative;}
		bool operator<=(const largeint& other)const{return *this<other||*this==other;}
		bool operator>(const largeint& other)const{return !(*this<=other);}
		bool operator>=(const largeint& other)const{return !(*this<other);}
		largeint operator+(const largeint& other)const{
			if(isNegative==other.isNegative){
				string a=num,b=other.num;
				int i=a.length()-1,j=b.length()-1,carry=0;
				string res;
				while(i>=0||j>=0||carry){
					int x=(i>=0)?(a[i--]-'0'):0;
					int y=(j>=0)?(b[j--]-'0'):0;
					int sum=x+y+carry;
					res.push_back(sum%10+'0');
					carry=sum/10;
				}
				reverse(res.begin(),res.end());
				largeint result(res);
				result.isNegative=isNegative;
				return result;
			}else{
				if(isNegative){
					largeint temp=*this;
					temp.isNegative=false;
					return other-temp;
				}else{
					largeint temp=other;
					temp.isNegative=false;
					return *this-temp;
				}
			}
		}
		largeint operator-(const largeint& other)const{
			if(isNegative!=other.isNegative){
				largeint temp=other;
				temp.isNegative=isNegative;
				return *this+temp;
			}
			string a=num,b=other.num;
			bool resNegative=false;
			if((isNegative&&*this>other)||(!isNegative&&*this<other)){
				swap(a,b);
				resNegative=true;
			}
			int i=a.length()-1,j=b.length()-1,borrow=0;
			string res;
			while(i>=0||j>=0){
				int x=(i>=0)?(a[i--]-'0'):0;
				int y=(j>=0)?(b[j--]-'0'):0;
				int diff=x-y-borrow;
				if(diff<0){
					diff+=10;
					borrow=1;
				}else{
					borrow=0;
				}
				res.push_back(diff+'0');
			}
			while(res.length()>1&&res.back()=='0')res.pop_back();
			reverse(res.begin(),res.end());
			largeint result(res);
			result.isNegative=resNegative;
			return result;
		}
		largeint operator*(const largeint& other)const{
			string a=num,b=other.num;
			int m=a.length(),n=b.length();
			vector<int> res(m+n,0);
			for(int i=m-1;i>=0;i--){
				for(int j=n-1;j>=0;j--){
					int mul=(a[i]-'0')*(b[j]-'0');
					int sum=mul+res[i+j+1];
					res[i+j+1]=sum%10;
					res[i+j]+=sum/10;
				}
			}
			string resultStr;
			for(int num:res){
				if(!(resultStr.empty()&&num==0)){
					resultStr.push_back(num+'0');
				}
			}
			if(resultStr.empty())resultStr="0";
			largeint result(resultStr);
			result.isNegative=isNegative^other.isNegative;
			return result;
		}
		void write()const{
			if(isNegative)cout<<"-";
			cout<<num;
		}
	};
}

using namespace largetype;

struct fantastic     {//这个也可以
	int len,s[9999];
	fantastic(){
		memset(s,0,sizeof(s));
		len=1;
	}
	fantastic operator=(const char*num){
		len=strlen(num);
		for(int i=0;i<len;++i)
			s[i]=num[len-i-1]-'0';
		return *this;
	}
	fantastic operator=(const int num){
		char a[9999];
		sprintf(a,"%lld",num);
		*this=a;
		return *this;
	}
	fantastic (const int num){*this=num;}
	fantastic (const char * num){*this=num;}
	fantastic operator+(const fantastic &a)   {
		fantastic c;
		c.len=max(len,a.len)+1;                
		for(int i=0,x=0;i<c.len;++i)
		{
			c.s[i]=s[i]+a.s[i]+x;
			x=c.s[i]/10;
			c.s[i]=c.s[i]%10;
		}
		if(c.s[c.len-1]==0)
			--c.len;
		return c;
	}
	fantastic operator * (const fantastic &x)           {
		fantastic c;
		c.len=len+x.len;                 
		for(int i=0;i<len;++i)
			for(int j=0;j<x.len;++j)
			{
				c.s[i+j]+=s[i]*x.s[j];
				c.s[i+j+1]+=c.s[i+j]/10;
				c.s[i+j]%=10;
			}
		if(c.s[c.len-1]==0)
			--c.len;
		return c;
	}
};


//另一种快读
/*
#include <bits/stdc++.h>
using lint = long long;

// #define DEBUG 1  // 调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}

~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
char gc() {
#if DEBUG  // 调试，可显示字符
return getchar();
#endif
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? ' ' : *p1++;
}

bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}

template <class T>
T read(T &x) {
double tmp = 1;
bool sign = 0;
x = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
if (ch == '.')
for (ch = gc(); isdigit(ch); ch = gc())
tmp /= 10.0, x += tmp * (ch - '0');
if (sign) x = -x;
return x;
}

void read(char *s) {
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
}

void read(char &c) { for (c = gc(); blank(c); c = gc()); }

void push(const char &c) {
#if DEBUG  // 调试，可显示字符
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}

template <class T>
void write(T x) {
if (x < 0) x = -x, push('-');  // 负数输出
static T sta[35];
T top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}

template <class T>
void write(T x, char lastChar) {
write(x), push(lastChar);
}
} io;

int main() {
int n = io.read(n);
lint sum = 0;
for (int t; n; --n) sum += io.read(t);
io.write(sum, '\n');
return 0;
}
*/
int Mod;//支持输入模值
int fastpow(int a,int b) {
	if(b==0)return 1;
	int sum=1;
	while(b) {
		if(b&1) sum=sum*a%Mod;
		a=a*a%Mod,b>>=1;
	}
	return sum;
}
//GetPrime(MAXP);MAXP为查询范围（查询到质数的最大值<=MAXP）
void FindPrime(){//查询质数
	int k;
	k=read();
	write(Prime[k]);
	puts("");
	return;
}
signed main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	//TODO
	int n;//个数
	int node_cnt,edge_cnt;//节点个数
	cin>>node_cnt>>edge_cnt;
	Graph dag(node_cnt);
	while(edge_cnt--){
		int u,v,w;
		cin>>u>>v>>w;
		dag.addedge(u,v,w);
	}
	dag.build_topo();
	
//	cin>>n;
//	for(int i=1;i<=n;i++)cin>>a[i];
//	MergeSort(1,n);
	int order_pairs=n*(n-1)/2-Reverse_order_pairs;
	//顺序对（请先MergeSort）
//	cout<<order_pairs;
	return 0;
	
}

高精度python卡法

PYTHON
from decimal import *
import sys
setcontext(Context(prec=2000000, Emax=2000000, Emin=0))
print((Decimal(sys.stdin.readline())-Decimal(sys.stdin.readline())))

分块模板

CPP
#include<bits/stdc++.h>
#define int long long
#define sint int
using namespace std;
const int MAXN=1000010;
int L[MAXN],R[MAXN],s[MAXN],a[MAXN],pos[MAXN],add[MAXN];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}//快读
inline void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}//快输
inline void update(int x,int y,int k){//在x,y范围每个内增加k
	int p=pos[x],q=pos[y];
	if(p==q){
		for(int i=x;i<=y;i++)a[i]+=k;
		s[p]=s[p]+(y-x+1)*k;
		return;
	}
	for(int i=p+1;i<=q-1;i++){
		add[i]+=k;
		s[i]=s[i]+(R[i]-L[i]+1)*k;
	}
	for(int i=x;i<=R[p];i++)a[i]+=k;
	s[p]=s[p]+(R[p]-x+1)*k;
	for(int i=L[q];i<=y;i++){
		a[i]+=k;
		s[q]+=k;
	}
}
int select(int x,int y){
	int p=pos[x],q=pos[y];
	int ans=0;
	if(p==q){
		for(int i=x;i<=y;i++)ans+=a[i]+add[p];
		return ans;
	}
	else {
		for(int i=x;i<=R[p];i++)ans+=a[i]+add[p];//左不完整块
		for(int i=p+1;i<=q-1;i++)ans+=s[i];//中间完整块
		for(int i=L[q];i<=y;i++)ans+=a[i]+add[q];//右不完整块
		return ans;
	}
	
}
int n,m,opt;

signed main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	int t=sqrt(n);
	for(int i=1;i<=t;i++){
		L[i]=t*(i-1)+1;
		R[i]=t*i;
		for(int j=L[i];j<=R[i];j++)pos[j]=i;
	}
	if(R[t]<n){
		t++;
		L[t]=R[t-1]+1;
		R[t]=n;
		for(int i=L[t];i<=R[t];i++)pos[i]=t;
	}
	for(int i=1;i<=t;i++){
		for(int j=L[i];j<=R[i];j++){
			s[i]+=a[j];
			pos[j]=i;
		}
	}
	while(m--){
		opt=read();
		if(opt==1){
			int x,y,k;
			x=read(),y=read(),k=read();
			update(x,y,k);
		}
		else {
			int x;
			x=read();
			write(a[x]+add[pos[x]]);
			puts("");
		}
	}
	
	return 0;
}

欧拉筛

CPP
#include <bits/stdc++.h>
using namespace std;
bitset<100000010> isPrime;
int Prime[6000010];
int cnt = 0;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
void GetPrime(int n)
{
	isPrime.set();

	isPrime[1] = 0;
	
	for(int i = 2; i <= n; i++)
	{
		if(isPrime[i])
			Prime[++cnt] = i; 
		
		for(int j = 1; j <= cnt && i*Prime[j] <= n; j++) 
		{
			isPrime[i*Prime[j]] = 0;
			
			if(i % Prime[j] == 0)
				break; 
		}
	}
}
void solve(){
	int k;
	k=read();
	write(Prime[k]);
	puts("");
	return;
}
signed main()
{
	long long n;int q;
	n=read();q=read();
	GetPrime(n);
	while (q--)
	{
		solve();
	}
	return 0;
}

线段树模板

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ls id<<1
#define rs id<<1|1
using namespace std;

inline int read(){//fastread
	int res=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)){ res=res*10+ch-48; ch=getchar();}
	return res*f;
}
const int maxn=100000+10;
struct Node{
	int L,R;
	int sum,lazy,ma;
} t[maxn*4];
int n,a[maxn];
void up(int id){
	t[id].sum=t[ls].sum+t[rs].sum;
	t[id].ma=max(t[ls].ma,t[rs].ma);
}
void down(int id){//下传
	t[ls].lazy+=t[id].lazy; t[rs].lazy+=t[id].lazy;
	t[ls].sum+=(t[ls].R-t[ls].L+1)*t[id].lazy;
	t[ls].ma+=t[id].lazy;
	t[rs].sum+=(t[rs].R-t[rs].L+1)*t[id].lazy;
	t[rs].ma+=t[id].lazy;
	t[id].lazy=0;
}
void build(int id,int l,int r){//建立
	t[id].L=l; t[id].R=r;
	if(l==r){
		t[id].sum=a[l]; t[id].ma=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(ls,l,mid); //左子树
	build(rs,mid+1,r);//右子树
	up(id);
}
void update(int id,int l,int r,int val){//将l，r区间同时加上一个val
	if(t[id].L>r || t[id].R<l) return;
	if(t[id].L>=l && t[id].R<=r){//节点自己处理
		t[id].lazy+=val;
		t[id].sum+=(t[id].R-t[id].L+1)*val;
		t[id].ma+=val;
		return;
	}
	if(t[id].lazy!=0) down(id);
	update(ls,l,r,val); update(rs,l,r,val);
	up(id);
}//修改操作
int ask_sum(int id,int l,int r){//查询元素的和
	if(t[id].L>r || t[id].R<l) return 0;
	if(t[id].L>=l && t[id].R<=r) return t[id].sum;
	if(t[id].lazy !=0) down(id);
	return ask_sum(ls,l,r)+ask_sum(rs,l,r);
}
int ask_max(int id,int l,int r){//查询区间最大值
	if(t[id].L>r || t[id].R<l) return -0x7f7f7f7f;
	if(t[id].L>=l && t[id].R<=r) return t[id].ma;
	if(t[id].lazy !=0) down(id);
	return max(ask_max(ls,l,r),ask_max(rs,l,r));
}
signed main(){
	int m,opt,l,r,val;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while(m--){
		cin>>opt;
		if(opt==1){
			cin>>l>>r>>val; update(1,l,r,val);
		} 
		else if(opt==2){
			cin>>l>>r;
			cout<<ask_sum(1,l,r)<<endl;
		} 
	}
	return 0;
}

扶苏线段树模板

CPP
#include<bits/stdc++.h>
//#define int long long
//#define endl '\n' 
#define ls id<<1
#define rs id<<1|1
#define getchar getchar_unlocked
#define putchar putchar_unlocked

typedef long long ll;
typedef short st;

using namespace std;
const ll maxn=1e6+10;
struct SegmentTree{
	int L,R;
	ll add,max,cov;
	bool used;//used?
} t[maxn<<2];
int n,m;
ll a[maxn];
void up(int id){
	t[id].max=max(t[ls].max,t[rs].max);
}
void down(int id){//下传
	if((t[id].used)){
		t[ls].cov=t[id].cov;
		t[rs].cov=t[id].cov;
		
		t[ls].add=t[id].add;
		t[rs].add=t[id].add;
		
		t[ls].max=t[id].add+t[id].cov;
		t[rs].max=t[id].add+t[id].cov;
		
		t[ls].used=1;t[rs].used=1;
		
		
	}
	else{//unused
		t[ls].add+=t[id].add;
		t[rs].add+=t[id].add;
		
		t[ls].max+=t[id].add;
		t[rs].max+=t[id].add;
		
		
		
	}
	t[id].add=t[id].cov=t[id].used=0;
	
}
void build(int id,int l,int r){//建立
	t[id].L=l; t[id].R=r;
	t[id].max=-1e18;
//	t[id].add=0;
//	t[id].cov=LLONG_MIN;
	if(l==r){
		t[id].max=a[l];
//		t[id].used=0;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid); //左子树
	build(rs,mid+1,r);//右子树
	up(id);
}

void change(int id,int l,int r,ll val){//updcov
//	if(l>t[id].R || t[id].L<r) return;
	if(l<=t[id].L&&t[id].R<=r){
		t[id].cov=val;
		t[id].add=0;
		t[id].max=val;
		t[id].used=1;
		return;
	}
	/*	if(t[id].add !=0)*/ down(id);
	int mid=(t[id].L+t[id].R)>>1;
	if(l<=mid)change(ls,l,r,val);
	if(mid+1<=r)change(rs,l,r,val);
	up(id);
	
}//覆盖操作

void update(int id,int l,int r,ll val){//updadd
//	if(t[id].L>r || t[id].R<l) return;
	if(t[id].L>=l && t[id].R<=r){//节点自己处理
		t[id].add+=val;
		t[id].max+=val;
		return;
	}
	down(id);
	int mid=(t[id].L+t[id].R)>>1;
	if(l<=mid)update(ls,l,r,val);
	if(mid+1<=r)update(rs,l,r,val);
	up(id);
}//修改操作


ll ask_max(int id,int l,int r){//查询区间最大值
	if(t[id].L>r || t[id].R<l) return -1e18;
	if(l<=t[id].L&&t[id].R<=r) 
		return t[id].max;
	/*	if(t[id].add !=0)*/ down(id);
	
	ll res=-1e18;
	int mid=(t[id].L+t[id].R)>>1;
	if(l<=mid)res=max(res,ask_max(ls,l,r));
	if(mid+1<=r)res=max(res,ask_max(rs,l,r));
	return res;
	
}
signed main(){
	int opt;
	int l,r;
	ll val;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--){
		scanf("%d%d%d",&opt,&l,&r);
		if(opt==1){
			scanf("%lld",&val);
			change(1,l,r,val);
			
		} 
		else if(opt==2){
			scanf("%lld",&val);
			update(1,l,r,val);
			
		} 
		else{
			printf("%lld\n",ask_max(1,l,r));
		}
	}
	return 0;
}

矩形周长

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl node_line
#define nt node_SegmentTree
#define ls id<<1
#define rs id<<1|1
#define endl '\n'
const int MAXN=1e5+10;//mod=998224353
int tot,ans,last;//last上条底的长度
int X[MAXN*2];//离散化

struct node_line{
	int Lx,Rx,y;
	int state;//状态
}line[MAXN*2];
struct node_SegmentTree{
	int L,R,cnt,len,sum; //cnt表示当前区间被覆盖的次数,len当先扫描到的矩形的长,sum不相交包含的竖边个类 
	bool lcov,rcov;
} t[MAXN*4];

bool cmp(nl a,nl b){
	if(a.y==b.y)return a.state>b.state;
	return a.y<b.y;
}
void build(int id,int l,int r){
	t[id].L=l;t[id].R=r;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(ls,l,mid);build(rs,mid+1,r);
}
void up(int id){
	int l=t[id].L,r=t[id].R;
	if(t[id].cnt>0){
		t[id].len=X[r+1]-X[l];
		
		t[id].lcov=t[id].rcov=1;
		t[id].sum=2;
	}
	else{
		t[id].len=t[ls].len+t[rs].len;
		t[id].sum=t[ls].sum+t[rs].sum;
		t[id].lcov=t[ls].lcov, t[id].rcov=t[rs].rcov;
		if(t[ls].rcov&&t[rs].lcov)t[id].sum-=2;
	}
}
void update(int id,int l,int r,int state){
	if (l<=t[id].L && t[id].R<=r) {
		t[id].cnt+=state;
		up(id);
		return;
	}
	int mid=(t[id].L+t[id].R)>>1;
	if(l<=mid)update(ls,l,r,state);
	if(r>mid)update(rs,l,r,state);
	up(id);
}
signed main(){
	last=tot=ans=0;
	int n,x,y,x2,y2;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>x2>>y2;
		line[i]={x,x2,y,1};
		line[i+n]={x,x2,y2,-1};
		X[i]=x;
		X[i+n]=x2;
	}
	n*=2;
	sort(line+1,line+n+1,cmp);
	sort(X+1, X+n+1);
	//去重离散化
	tot=unique(X+1, X+n+1)-X-1;
	build(1,1,tot);//建立线段树
	for(int i=1;i<n;i++) {
		int L=lower_bound(X+1,X+tot+1,line[i].Lx)-X;
		int R=lower_bound(X+1,X+tot+1,line[i].Rx)-X;
		update(1,L,R-1,line[i].state);
		ans=ans+abs(last-t[1].len);//横边长度
		last=t[1].len;
		ans=ans+t[1].sum*(line[i+1].y-line[i].y); 
	}
	ans=ans+line[n].Rx-line[n].Lx; 
	cout<<ans<<endl;
	return 0;
}

矩形面积并

CPP
#include<bits/stdc++.h>
#define int long long
#define nl node_line
#define nt node_SegmentTree
#define ls id<<1
#define rs id<<1|1
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN=200000+10;
struct node_SegmentTree{
	int L,R;
	int cnt,len;
}t[MAXN*8];
struct node_line{
	int l,r,h,state;
}a[MAXN*2];

int n,maxv=0,b[MAXN*2];

bool cmp(nl a,nl b){
	return a.h<b.h;
}
void build(int id,int l,int r){
	t[id].L=l;t[id].R=r;
	if(t[id].L==t[id].R)return;
	int mid=(l+r)>>1;
	build(ls,l,mid);build(rs,mid+1,r);
}
void update(int id,int l,int r,int state){
	if(t[id].L>r||t[id].R<l)return;
	if(t[id].L>=l&&t[id].R<=r){
		t[id].cnt+=state;
		if(t[id].cnt==0){
			t[id].len=t[ls].len+t[rs].len;
		}
		else t[id].len=b[t[id].R+1]-b[t[id].L];
		return;
	}
	update(ls,l,r,state);update(rs,l,r,state);
	if(t[id].cnt==0){
		t[id].len=t[ls].len+t[rs].len;
	}
	else t[id].len=b[t[id].R+1]-b[t[id].L];
}
signed main(){
	int x,y,x2,y2;
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>x2>>y2;
		if(x>x2){swap(x,x2),swap(y,y2);}
		maxv=max(maxv,x2);
		a[i*2-1].h=min(y,y2); 
		a[i*2-1].l=x; 
		a[i*2-1].r=x2; 
		a[i*2-1].state=1;
		a[i*2].h=max(y,y2); 
		a[i*2].l=x; a[i*2].r=x2; 
		a[i*2].state=-1;
		b[i*2-1]=x; 
		b[i*2]=x2;
	}
	n*=2;
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1);
	int tot=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++){
		int xl=lower_bound(b+1,b+tot+1,a[i].l)-b;
		int xr=lower_bound(b+1,b+tot+1,a[i].r)-b;
		a[i].l=xl; a[i].r=xr;
	}
	build(1,1,tot);
	int now=a[1].h;
	
	update(1,a[1].l,a[1].r-1,a[1].state);
	int ans=0;
	for(int i=2;i<=n;i++){
		int len=t[1].len;
		ans+=len*(a[i].h-now);
		now=a[i].h;
		update(1,a[i].l,a[i].r-1,a[i].state);
	}
	cout<<ans<<endl;
	return 0;
}

普通平衡树（离散化权值线段树）

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
//该题是一个权值线段树离线算法实现平衡树，如果强制在线就不行
const int maxn=100000+10;
struct node {
	int l,r,cnt;//sum表示数值范围内，数字出现的总次数
} tr[maxn*4];
int a[maxn],b[maxn],n,opt[maxn],tot=0,p;
inline void build(int id,int l,int r) {
	tr[id].l=l;
	tr[id].r=r;
	if(l==r) return;
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
}
inline void update(int id,int l,int r,int x) {
	if(tr[id].l>r || tr[id].r<l) return;
	if(tr[id].l>=l && tr[id].r<=r) {
		tr[id].cnt+=x;
		return;
	}
	update(id*2,l,r,x);
	update(id*2+1,l,r,x);
	tr[id].cnt=tr[id*2].cnt+tr[id*2+1].cnt;
}
int q_rank(int id,int l,int r) { //查询数字在l-r范围内出现的个数
	if(tr[id].l>r || tr[id].r<l) return 0;
	if(tr[id].l>=l && tr[id].r<=r) return tr[id].cnt;
	return q_rank(id*2,l,r)+q_rank(id*2+1,l,r);
}
int q_num(int id,int x) {//查询当前线段树，出现次数为x的数
	if(tr[id].l==tr[id].r) return tr[id].l;
	if(x<=tr[id*2].cnt) return q_num(id*2,x);
	else return q_num(id*2+1,x-tr[id*2].cnt);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; i++) { //把要用到的操作和数存下来
		cin>>opt[i]>>a[i];
		if(opt[i]!=4) b[++tot]=a[i];
	}
	sort(b+1,b+tot+1);
	tot=unique(b+1,b+tot+1)-b-1;//去重
	build(1,1,tot);
	for(int i=1; i<=n; i++) { //枚举操作
		if(opt[i]!=4) p=lower_bound(b+1,b+tot+1,a[i])-b;//因为4操作不是对数值操作
		if(opt[i]==1) update(1,p,p,1);//插入x
		if(opt[i]==2) update(1,p,p,-1);//删除x
		if(opt[i]==3) { //查询数x的排名,排名定义为比当前数小的数的个数+1
			if(p==1) cout<<1<<endl;
			else cout<<q_rank(1,1,p-1)+1<<endl;
		}
		if(opt[i]==4) { //排名为x的数,即出现的数字个数为x的数值
			int k=q_num(1,a[i]);
			cout<<b[k]<<endl;//注意离散化后的，所以需要还原
		}
		if(opt[i]==5) { //查询x的前驱
			int rk=q_rank(1,1,p-1);//先找到当前小于等于p-1的个数
			int k=q_num(1,rk);//再查询个数对应的数值
			cout<<b[k]<<endl;
		}
		if(opt[i]==6) { //查询数字x的后继
			int rk=q_rank(1,1,p)+1;//先找到当前小于等于p的个数+1
			int k=q_num(1,rk);//再查询个数对应的数值
			cout<<b[k]<<endl;
		}
	}
	return 0;
}

普通平衡树（平衡树）

有旋Treap

CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+10;
int root=0,k;
struct treap{
	int ls,rs;
	int val,pri;
	int cnt,size;
}t[MAXN];
void up(int id){t[id].size=t[t[id].ls].size+t[t[id].rs].size+t[id].cnt;}
void zag(int &rt){//左旋
	int b=t[rt].rs;
	t[rt].rs=t[b].ls;
	t[b].ls=rt;
	up(rt);up(b);
	rt=b;
}
void zig(int &rt){//右旋
	int b=t[rt].ls;
	t[rt].ls=t[b].rs;
	t[b].rs=rt;
	up(rt);up(b);
	rt=b;
}
void insert(int &rt,int x){
	if(rt==0){
		t[++k].val=x;
		t[k].cnt=t[k].size=1;
		t[k].pri=rand()%1145140;
		rt=k;
		return;
	}
	t[rt].size++;
	if(x==t[rt].val){
		t[rt].cnt++;
		return;
	}
	if(x<t[rt].val){
		insert(t[rt].ls,x);
		if(t[t[rt].ls].pri<t[rt].pri)zig(rt);
	}
	else{
		insert(t[rt].rs,x);
		if(t[t[rt].rs].pri<t[rt].pri)zag(rt);
	}
}
void del(int &rt,int x){
	if(rt==0)return;
	if(t[rt].val==x){
		if(t[rt].cnt>1){
			t[rt].cnt--;
			t[rt].size--;
			return;
		}
		if(t[rt].ls==0||t[rt].rs==0){
			rt=t[rt].ls+t[rt].rs;
		}
		else{
			if(t[t[rt].ls].pri<t[rt].pri){
				zig(rt);del(rt,x);
			}
			else{
				zag(rt);del(rt,x);	
			}
		}
	}
	else if(x<t[rt].val){
		t[rt].size--;del(t[rt].ls,x);
	}
	else {
		t[rt].size--;del(t[rt].rs,x);
	}
}
int fRank(int rt,int x){
	if(rt==0)return 1;
	if(x==t[rt].val)return t[t[rt].ls].size+1;
	if(t[rt].val<x)return t[t[rt].ls].size+t[rt].cnt+fRank(t[rt].rs,x);
	else return fRank(t[rt].ls,x);
}
int fVal(int rt,int x){
	if(rt==0)return 0;
	if(t[t[rt].ls].size>=x)return fVal(t[rt].ls,x);
	else if(t[t[rt].ls].size+t[rt].cnt<x)return fVal(t[rt].rs,x-t[t[rt].ls].size-t[rt].cnt);
	else return t[rt].val;
}
const int INF=0x7f7f7f7f;
int fPre(int rt,int x){
	if(rt==0)return -INF;
	if(t[rt].val<x)return max(t[rt].val,fPre(t[rt].rs,x));
	else return fPre(t[rt].ls,x);
}
int fNext(int rt,int x){
	if(rt==0)return INF;
	if(t[rt].val>x)return min(t[rt].val,fNext(t[rt].ls,x));
	else return fNext(t[rt].rs,x);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	srand(time(NULL));
	memset(t,0,sizeof(t));
	int m,n,opt,v,xx,ans=0,last=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>v;
		insert(root,v);
	}
	while(m--){
		cin>>opt>>xx;
		int x=xx^last;
		if(opt==1)insert(root,x);
		if(opt==2)del(root,x);
		if(opt==3){last=fRank(root,x);ans=ans^last;}
		if(opt==4){last=fVal(root,x);ans=ans^last;}
		if(opt==5){last=fPre(root,x);ans=ans^last;}
		if(opt==6){last=fNext(root,x);ans=ans^last;}
	}
	cout<<ans;
	return 0;
}

FHQ Treap

CPP
#include<bits/stdc++.h>
using namespace std;
const signed int MAXN=1.1e6;
struct FHQNode{
	int ls,rs;
	int val,pri,size;
}t[MAXN];
int tot=0,root=0,n,m,opt,Fx,last=0,Tx;
void up(int id){t[id].size=t[t[id].ls].size+t[t[id].rs].size+1;return;}
void crt_node(int x){//新建
	++tot;
	t[tot].size=1;
	t[tot].ls=t[tot].rs=0;
	t[tot].val=x;
	t[tot].pri=rand();
	return;
}
void split(int u,int x,int &L,int &R){
	if(u==0){L=R=0;return;}
	if(t[u].val<=x){
		L=u;//左边确定
		split(t[u].rs,x,t[u].rs,R);
	}
	else{
		R=u;//右边确定
		split(t[u].ls,x,L,t[u].ls);
	}
	up(u);
	return;
}
int merge(int L,int R){
	if(L==0||R==0)return L+R;
	if(t[L].pri>t[R].pri){
		t[L].rs=merge(t[L].rs,R);
		up(L);
		return L;
	}
	else{
		t[R].ls=merge(L,t[R].ls);
		up(R);
		return R;
	}
}
int insert(int x){
	int L,R;
	split(root,x,L,R);
	crt_node(x);
	root=merge(merge(L,tot),R);
	return tot;
}
int deldot(int x){//删除第一个值为x的点
	int L,R,mid;
	split(root,x,L,R);
	split(L,x-1,L,mid);
	mid=merge(t[mid].ls,t[mid].rs);
	root=merge(merge(L,mid),R);
	return root;
}
int delall(int x){//删除所有的值为x的点
	int L,R,mid;
	split(root,x,L,R);
	split(L,x-1,L,mid);
	root=merge(L,R);
	return root;
}
int fRank(int x){
	int L,R,ans;
	split(root,x-1,L,R);
	ans=t[L].size+1;
	root=merge(L,R);
	return ans;
}
int kth(int u,int k){
	if(k==t[t[u].ls].size+1)return u;
	if(k<=t[t[u].ls].size)return kth(t[u].ls,k);
	return kth(t[u].rs,k-t[t[u].ls].size-1);
}
int fPre(int x){
	int L,R,ans;
	split(root,x-1,L,R);
	ans=t[kth(L,t[L].size)].val;
	root=merge(L,R);
	return ans;
}
int fNext(int x){
	int L,R,ans;
	split(root,x,L,R);
	ans=t[kth(R,1)].val;
	root=merge(L,R);
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int v;
		cin>>v;
		insert(v);
	}
	int ans=0;
	while(m--){
		cin>>opt>>Fx;
		Tx=Fx^last;
		if(opt==1)insert(Tx);
		else if(opt==2)deldot(Tx);
		else if(opt==3)last=fRank(Tx),ans^=last;
		else if(opt==4)last=t[kth(root,Tx)].val,ans^=last;
		else if(opt==5)last=fPre(Tx),ans^=last;
		else if(opt==6)last=fNext(Tx),ans^=last;
	}
	cout<<ans;
	return 0;
}

树链剖分/重链剖分

CPP
#include<bits/stdc++.h>
#define ls id<<1
#define rs id<<1|1
#define int long long// use long long is very important!
using namespace std;
int dep[100001],fa[100001],head[100001],siz[100001],son[100001],top[100001],tid[100001],pos[100001],tot=0,ord=0;
int a[100001];
int n,m,root,p,opt;//son:重儿子,tid和pos处理树上与链上的映射
struct edge{
	int to,nxt;
}ed[100001*2];
struct SegmentTreeNode{
	int L,R;
	int sum,lazy;
} t[100001*4];

inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}//快读
inline void write(int x){
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
	//puts("");
}//快输

void addedge(int a,int b){
	ed[++tot].to=b;
	ed[tot].nxt=head[a];
	head[a]=tot;
}
void dfs1(int id,int father){
	dep[id]=dep[father]+1;
	fa[id]=father;
	siz[id]=1;
	son[id]=0;
	for(int i=head[id];i;i=ed[i].nxt){
		int t=ed[i].to;
		if(t!=father){
			dfs1(t,id);
			siz[id]+=siz[t];
			if(siz[t]>siz[son[id]])son[id]=t;
		}
	}
}
void dfs2(int id,int topp){//树链剖分
	top[id]=topp;
	pos[id]=++ord;
	tid[ord]=id;
	if(!son[id])return;
	dfs2(son[id],topp);
	for(int i=head[id];i;i=ed[i].nxt){
		int t=ed[i].to;
		if(t!=son[id]&&t!=fa[id])dfs2(t,t);
	}
}

void up(int id){
	t[id].sum=(t[ls].sum+t[rs].sum);
}
void down(int id){//处理编号id的为标记，下传给它的儿子
	if (!t[id].lazy) return;
	t[ls].lazy+=t[id].lazy;
	t[rs].lazy+=t[id].lazy;
	t[ls].sum+=((t[ls].R-t[ls].L+1)*t[id].lazy);
	t[rs].sum+=((t[rs].R-t[rs].L+1)*t[id].lazy);
	t[id].lazy=0;
}
void build(int id,int l,int r){
	t[id].L=l,t[id].R=r;
	t[id].lazy=0;t[id].sum=0;
	if(l==r){t[id].sum=a[tid[l]];return;}
	int mid=(l+r)>>1;
	build(ls,l,mid);build(rs,mid+1,r);
	up(id);
}
void update(int id,int l,int r,int val){//将l，r区间同时加上一个val
	if(t[id].L>r || t[id].R<l) return;
	if(t[id].L>=l && t[id].R<=r){//节点自己处理
		t[id].lazy+=val;
		t[id].sum+=(t[id].R-t[id].L+1)*val;
		return;
	}
	if(t[id].lazy!=0) down(id);
	int mid=(t[id].L+t[id].R)>>1;
	if(l<=mid)update(ls,l,r,val);
	if(r>mid)update(rs,l,r,val);
	up(id);
}

int ask_sum(int id,int l,int r){
	if(t[id].L>r || t[id].R<l) return 0;
	if(t[id].L>=l && t[id].R<=r) return t[id].sum;
	if(t[id].lazy !=0) down(id);
	return (ask_sum(ls,l,r)+ask_sum(rs,l,r));
}
void tree_update(int u,int v,int val){//树上更新
	//不同重链
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);//先从top的depth深的那条重链开始
		update(1,pos[top[u]],pos[u],val);
		u=fa[top[u]];//轻边
	}
	//同一重链
	if(dep[u]>dep[v])swap(u,v);
	update(1,pos[u],pos[v],val);
}
void subtree_update(int id,int val){//子树树上更新
	update(1,pos[id],pos[id]+siz[id]-1,val);
}
void node_update(int id,int x, int val) {
	if (t[id].L==t[id].R) {
		t[id].sum+=val;
		return;
	}
	down(id);
	int mid = (t[id].L+t[id].R)>>1;
	if (x<=mid)node_update(ls,x,val);
	else node_update(rs,x,val);
	up(id);
}
int tree_sum(int u,int v){
	int sum=0;
	//不同重链
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);//先从top的depth深的那条重链开始
		sum+=ask_sum(1,pos[top[u]],pos[u]);
		u=fa[top[u]];//轻边
	}
	//同一重链
	if(dep[u]>dep[v])swap(u,v);
	sum+=ask_sum(1,pos[u],pos[v]);
	return sum;
}
int subtree_sum(int id){
	return ask_sum(1,pos[id],pos[id]+siz[id]-1);
}
signed main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	memset(head,0,sizeof(head));
	n=read();m=read();
	root=1;p=2147483647;
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	
	for(int i=1;i<n;i++){
		int x,y;
		x=read();y=read();
		addedge(x,y);addedge(y,x);
	}
	
	dfs1(root,0);
	dfs2(root,root);
	build(1,1,n);
	while(m--){
		opt=read();
		
	return 0;
}

点分治

CPP
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+50;
struct ed{
	int v,w;
};
vector<ed>e[N];
int root,dep[N],f[N],siz[N],n,k,m,que[N],S,tot,len[N];
bool vis[N],ans[10000001];
void getroot(int u,int fa){
	f[u]=0,siz[u]=1;
	for(auto x:e[u]){
		int v=x.v;
		if(vis[v]||v==fa)continue;
		getroot(v,u);
		siz[u]+=siz[v];
		f[u]=max(f[u],siz[v]);
	}
	f[u]=max(f[u],S-siz[u]);
	if(f[u]<f[root])root=u;
}
void getdep(int u,int fa){
	for(auto x:e[u]){
		int v=x.v,w=x.w;
		if(v==fa||vis[v])continue;
		dep[v]=dep[u]+w;
		len[++tot]=dep[v];
		if(len[tot]<=10000000)ans[len[tot]]=1;
		getdep(v,u);
	}
}
void getans(int u){
	vector<int> total;
	total.push_back(0);
	for(auto x:e[u]){
		int v=x.v,w=x.w;
		if(vis[v])continue;
		tot=0;
		dep[v]=w;
		len[++tot]=w;
		if(w<=10000000)ans[w]=1;
		getdep(v,u);
		for(int i=1;i<=tot;i++){
			for(int d:total){
				int sum=len[i]+d;
				if(sum<=10000000)ans[sum]=1;
			}
		}
		for(int i=1;i<=tot;i++)total.push_back(len[i]);
	}
}
void sol(int u){
	vis[u]=1;
	getans(u);
	for(auto x:e[u]){
		int v=x.v;
		if(vis[v])continue;
		S=siz[v];
		root=0,f[root]=N;
		getroot(v,0);
		sol(root);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,cu,cv,cw;i<n;i++){
		scanf("%d%d%d",&cu,&cv,&cw);
		e[cu].push_back({cv,cw});
		e[cv].push_back({cu,cw});
	}
	for(int i=1;i<=m;i++)scanf("%d",&que[i]);
	S=n,f[0]=N,root=0;
	getroot(1,0);
	sol(root);
	for(int i=1;i<=m;i++)puts(ans[que[i]]?"AYE":"NAY");
}

缩点

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100050;
int a[maxn],dfn[maxn],low[maxn],instack[maxn],ord=0,color[maxn],sum[maxn],color_cnt=0,rudu[maxn],dis[maxn],n,m,ans=0;
//color：强连通编号 sum：强连通权值和 color_cnt：强连通个数
vector<int> G[maxn],G2[maxn];
stack<int> stk;
void tarjan(int u){
	dfn[u]=low[u]=++ord;
	stk.push(u);
	instack[u]=1;
	for(int v:G[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(instack[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		color_cnt++;
		while(true){
			int v=stk.top();
			color[v]=color_cnt;
			instack[v]=0;
			sum[color_cnt]+=a[v];
			stk.pop();
			if(u==v)break;
		}
	}
	
}
void tp(){//拓扑
	queue<int>q;
	for(int i=1;i<=color_cnt;i++){
		if(!rudu[i]){
			q.push(i);
			dis[i]=sum[i];
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i:G2[u]){
			dis[i]=max(dis[i],dis[u]+sum[i]);
			if(--rudu[i]==0)q.push(i);
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,dis[i]);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
	for(int u=1;u<=n;u++){
		int uu=color[u];
		for(int v:G[u]){
			int vv=color[v];
			if(uu!=vv){
				G2[uu].push_back(vv);
				rudu[vv]++;
			}
		}
	}
	tp();
	cout<<ans;
	return 0;
}

字典树

CPP
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
struct cnt_trie{
	vector<vector<int>>ch;
	vector<int>cnt;
	int ct=0;
	int gn_map[128];
	//如果用全局数组，不用vector，常数约为1/2
	void clear(){
		ch.clear();
		cnt.clear();
		ch.push_back(vector<int>(65, 0)); // 初始化根节点
		cnt.push_back(0);
		ct=0;
	}
	cnt_trie(){cnt_trie::init_gn();clear();}
    void init_gn() {
        for(int i=0;i<128;i++) gn_map[i]=-1;
        for(char c='A';c<='Z';c++) gn_map[c]=c-'A';
        for(char c='a';c<='z';c++) gn_map[c]=c-'a'+26;
        for(char c='0';c<='9';c++) gn_map[c]=c-'0'+52;
    }
	inline int gn(char x){return gn_map[(int)x];}
	void insert(string str){
		int p=0,l=str.size();
		for(int i=0;i<l;i++){
			int c=gn(str[i]);
			if(!ch[p][c]){
				ch.push_back(vector<int>(65, 0));//全局数组就不用这两个push_back，直接用
				cnt.push_back(0);
				ch[p][c]=++ct;
			}
			p=ch[p][c];
			cnt[p]++;
		}
	}
	int find_cnt(string str){
		int p=0,l=str.size();
		for(int i=0;i<l;i++){
			int c=gn(str[i]);
			if(!ch[p][c]) return 0;
			p=ch[p][c];
		}
		return cnt[p];
	}
	pair<int,int> find_range(string str){
		int p=0,l=str.size();
		for(int i=0;i<l;i++){
			int c=gn(str[i]);
			if(!ch[p][c]) return {0,0};
			p=ch[p][c];
		}
		return {p,ct};
	}
};
int main(){
	int T;
	cin>>T;
	cnt_trie tri;
	while(T--){
		tri.clear();
		int n,q;
		cin>>n>>q;
		while(n--){
			string s;
			cin>>s;
			tri.insert(s);
		}
		while(q--){
			string qr;
			cin>>qr;
			cout<<tri.find_cnt(qr)<<endl;
		}
	}
	return 0;
}

文艺平衡树

CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=2*114514;
struct FHQNode{
	int ls,rs;
	int val,pri,size;
	int lazy;
}t[maxn];
int tot=0,root=0,n,m;
void crt_node(int x){
	++tot;
	t[tot].size=1;
	t[tot].lazy=t[tot].ls=t[tot].rs=0;
	t[tot].val=x;
	t[tot].pri=rand();
	return;
}
void up(int id){
	t[id].size=t[t[id].ls].size+t[t[id].rs].size+1;
}
void down(int id){
	if(t[id].lazy){
		swap(t[id].ls,t[id].rs);
		t[t[id].ls].lazy^=1;
		t[t[id].rs].lazy^=1;
		t[id].lazy=0;
	}
}
void split(int id,int x,int &L,int &R){
	if(id==0){L=R=0;return;}
	down(id);
	if(t[t[id].ls].size+1<=x){
		L=id;
		split(t[id].rs,x-t[t[id].ls].size-1,t[id].rs,R);
	}
	else {
		R=id;
		split(t[id].ls,x,L,t[id].ls);
	}
	up(id);
	return;
}
int merge(int L,int R){
	if(L==0||R==0)return L+R;
	if(t[L].pri>t[R].pri){
		down(L);
		t[L].rs=merge(t[L].rs,R);
		up(L);
		return L;
	}
	else{
		down(R);
		t[R].ls=merge(L,t[R].ls);
		up(R);
		return R;
	}
}
void print(int id){
	if(id==0)return;
	down(id);
	
	print(t[id].ls);
	printf("%d ",t[id].val);
	print(t[id].rs);//中序遍历
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		crt_node(i);
		root=merge(root,tot);
	}
	while(m--){
		int l,r,L,R,mid;
		cin>>l>>r;
		split(root,r,L,R);
		split(L,l-1,L,mid);
		t[mid].lazy^=1;
		root=merge(merge(L,mid),R);
	}
	print(root);
	return 0;
}

网络流

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=205,M=5005,inf=2147483647;
int n,m,s,t;
int dis[N];
struct edge{
	int l,r,c;
	int nxt;
}ed[M*2];
int head[N],cnt=2;
void adde(int l,int r,int c){
	ed[cnt].l=l;
	ed[cnt].r=r;
	ed[cnt].c=c; 
	ed[cnt].nxt=head[l];
	head[l]=cnt;
	cnt++; 
}
bool bfs(){
	queue<int> q;
	for(int i=1;i<=n;i++) dis[i]=-1;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int curr=q.front();
		q.pop();
		for(int i=head[curr];i;i=ed[i].nxt){
			if(dis[ed[i].r]==-1&&ed[i].c>0){
				dis[ed[i].r]=dis[curr]+1;  
				q.push(ed[i].r);
				if(ed[i].r==t)return 1;
			}
		}
	}
	return(dis[t]!=-1);
}
int dfs(int start,int flow){
	int cnt=0; 
	if(start==t) return flow;
	for(int i=head[start];i&&flow;i=ed[i].nxt){ 
		if((ed[i].c>0)&&(dis[ed[i].r]==dis[start]+1)){
			int ret=dfs(ed[i].r,min(flow,ed[i].c)); 
			if(ret==0)dis[ed[i].r]=inf;
			if(ret>0){
				ed[i].c-=ret; 
				ed[i^1].c+=ret;
				cnt+=ret;
				flow-=ret; 
			}
		}
	}	
	return cnt; 
}
void dinic(){
	int ans=0;
	while(bfs()){ 
		ans+=dfs(s,inf);
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adde(u,v,w);
		adde(v,u,0);
	}
	dinic();
	return 0;
}

二分图

CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
vector<int> G[maxn];
int match[maxn],ans=0;
bool matched[maxn];
bool find(int u){
	for(int v:G[u]){
		if(!matched[v]){
			matched[v]=1;
			if(!match[v]||find(match[v])){
				match[v]=u;
				return true;
			}
		}
	}
	return false;
}
int main(){	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,e;
	cin>>n>>m>>e;
	for(int i=0;i<e;i++){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		memset(matched,0,sizeof(matched));
		if(find(i))ans++;
	}
	cout<<ans;
	return 0;
}

Dijkstra

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1100010,inf=0x7fffffff;
struct edge{
	int to,w;
};
vector<edge> G[maxn];
struct qnode{
	int id,val;
	qnode(int d,int v){id=d; val=v;}
	bool friend operator<(qnode n1,qnode n2)
	{
		return n1.val>n2.val;
	}
};
int dis[maxn],n,m,s;
bool vis[maxn];
priority_queue<qnode> q;
void dijkstra(){
	for(int i=1;i<=n;i++)dis[i]=inf;
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	q.push(qnode(s,0));
	while(!q.empty()){
		qnode qnd=q.top();q.pop();
		int u=qnd.id;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].to,w=G[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(qnode(v,dis[v]));//松弛
			}
		}
	}
}
signed main(){	
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	dijkstra();
	for(int i=1;i<=n;i++){
		if(dis[i]==inf) cout<<(1<<31)-1<<' ';
		else cout<<dis[i]<<' ';
	}
	return 0;
}

可持久化线段树1

CPP
//“你说得对，但是主席树十分持♂久♂，因为它可→持↑久↓化→”
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e7+100;
int cnt=1,a[MAXN],n,m,roots[MAXN];

struct Tree{
	int L,R,val;
}t[MAXN*4];

inline int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}return x*f;}//快读
inline void write(int x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}//快输

int crt_node(int id){
	cnt++;
	t[cnt]=t[id];
	return cnt;
}
int build(int id,int l,int r){
	id=++cnt;
	if(l==r){
		t[id].val=a[l];
		return cnt;
	}
	int mid=(l+r)>>1;
	t[id].L=build(t[id].L,l,mid);
	t[id].R=build(t[id].R,mid+1,r);
	return id;
}
int update(int id,int l,int r,int x,int val){
	id=crt_node(id);
	if(l==r)t[id].val=val;
	else{
		int mid=(l+r)>>1;
		if(x<=mid)t[id].L=update(t[id].L,l,mid,x,val);
		else t[id].R=update(t[id].R,mid+1,r,x,val);
	}
	return id;	
}
int ask(int id,int l,int r,int x){
	if(l==r)return t[id].val;//单点
	int mid=(l+r)>>1;
	if(x<=mid)return ask(t[id].L,l,mid,x);//在左
	else return ask(t[id].R,mid+1,r,x);//在右
}
int main(){
	int v,loc,val;
	int opt;
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	roots[0]=build(0,1,n);
	for(int i=1;i<=m;i++){
		v=read();opt=read();loc=read();
		if(opt==1){
			val=read();
			roots[i]=update(roots[v],1,n,loc,val);
		}
		else{
			write(ask(roots[v],1,n,loc)),puts("");
			roots[i]=roots[v];
		}
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...