笛卡尔树

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int n,p[N],s[N],tot,l[N],r[N],flag,root;
int q[N],head,tail;long long ans1,ans2;
signed main(){
	n=read();for(int i=1;i<=n;i++)p[i]=read();
	for(int i=1;i<=n;i++){
		flag=0;
		while(tot && p[s[tot]]>p[i])tot--,flag=1;
		if(tot)r[s[tot]]=i;
		else root=i;
		if(flag)l[i]=s[tot+1];
		s[++tot]=i;
	}
	q[++tail]=root;head=1;
	while(head<=tail){
		ans1^=(long long)q[head]*(l[q[head]]+1),ans2^=(long long)q[head]*(r[q[head]]+1);
		if(l[q[head]])q[++tail]=l[q[head]];
		if(r[q[head]])q[++tail]=r[q[head]];
		head++;
	}
	printf("%lld %lld\n",ans1,ans2);
	return 0;
}

树状数组

int lowbit(int x){
	return x&(-x);
}
void add(int i,int k){
	for(int j=i;j<=n;j+=lowbit(j))c[j]+=k;
	return;
}
int getsum(int i){
	int res=0;for(int j=i;j>0;j-=lowbit(j))res+=c[j];
	return res; 
}

树状数组（区间修改 区间查询）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=201000;
ll n,m;
ll a[N],b[N],c[N],t[N],t1,t2,t3,t4;
ll lowbit(ll x){
	return x&(-x);
}
void add(ll x,ll y){
	for(ll i=x;i<=n;i+=lowbit(i))
		c[i]+=y;
	return;
}
void addt(ll x,ll y){
	for(ll i=x;i<=n;i+=lowbit(i))
		t[i]+=y;
	return;
}
ll ask(ll x){
	ll res=0;
	for(ll i=x;i;i-=lowbit(i))
		res+=c[i];
	return res;
}
ll askt(ll x){
	ll res=0;
	for(ll i=x;i;i-=lowbit(i))
		res+=t[i];
	return res;
}
ll search(ll x){
	return ask(x)*(x+1)-askt(x);
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i]-a[i-1];
		add(i,b[i]);
		addt(i,b[i]*i);
	}
	for(int i=1;i<=m;i++){
		cin>>t1;
		if(t1==1){
			cin>>t2>>t3>>t4;
			add(t2,t4),add(t3+1,-t4);
			addt(t2,t4*t2),addt(t3+1,-(t4*(t3+1)));
		}
		if(t1==2){
			cin>>t2>>t3;
			cout<<search(t3)-search(t2-1)<<endl;
		}
	}
	return 0;
}

树状数组+值域

#include<bits/stdc++.h>
#define N 200020
#define lowbit(i) (i&-i)
using namespace std;
pair<int, int> a[N];
int DP[N], C[N];
void ins(int x, int c) {
    for (int i = x; i < N; i += lowbit(i))
        C[i] = max(C[i], c);
}
int ask(int x) {
    int ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans = max(ans, C[i]);
    return ans;
}
int main() {
    int n, v;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> v;
        a[i].first = v; a[i].second = i + 1;
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++)
        DP[i] = ask(a[i].second) + 1,
        ins(a[i].second, DP[i]);
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, DP[i]);
    cout << ans << endl;
}

二维树状数组

#include<bits/stdc++.h>
using namespace std;
int c[310][310],mp[310][310];
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
int lowbit(int v){
	return v&(-v);
}
void add(int x,int y,int va){
	for(int i=x;i<=300;i+=lowbit(i))
		for(int j=y;j<=300;j+=lowbit(j))
			c[i][j]+=va;
	return;
}
int query(int x,int y){
	int res=0;
	for(int i=x;i;i-=lowbit(i))
		for(int j=y;j;j-=lowbit(j))
			res+=c[i][j];
	return res;
} 
int n,m,Q,opt,t1,t2,t3,t4,k;
int main(){
	return 0;
}