A数列下标

题意：给出n个元素A数组，定义B数组为A数组下标右边第一个比该元素大的下标，如果没找到则为0.
解法：单调栈，维护单调递减栈，每次被弹出的元素下标的第一个比该元素大的值，为当前遍历下标值。

#include<bits/stdc++.h>
typedef  long long ll ;
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 2e5+9;
const int maxn = 1e4+9;
int a[maxn];
int st[maxn] , top ;
int b[maxn];
void solve(){
    int n ;
    scanf("%lld" , &n);
    a[n+1] = -INF ;
    rep(i , 1 , n){
        scanf("%lld" , &a[i]);
        while(top && a[i] > a[st[top]]){
            b[st[top]] = i ;
            top--;
        }
        st[++top] = i ;
    }
    rep(i , 1 , n){
        cout << b[i] << " " ;
    }
    cout << endl;

}

signed main()
{
/*#ifdef ONLINE_JUDGE
#else
    freopen("D:\\c++\\out.txt", "w", stdout);
#endif*/
    //int _ ;cin>>_;while(_--)
        solve() ;
}

B可持久化动态图上树状数组维护01背包

题意：给出一个n长序列，每次可以从任意位置i花费ai * i 的代价来把ai删除，删除后后面元素依次补上
问删完所有元素的最小代价为多少？
解法：很容易想到：如果序列全为正数，则一直删除第一个元素，代价最小。
如果全为负数，则一直删最后一个。
那么一般情况，则优先删除负数，再删正数

#include<bits/stdc++.h>
typedef  long long ll ;
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 2e5+9;
const int maxn = 1e6+9;
int a[maxn];
int st[maxn] , top ;
int b[maxn];

bool cmp(int a,  int b){
    return a > b ;
}

void solve(){
    int n , ans = 0;
    scanf("%lld" , &n);
    rep(i , 1 , n){
        scanf("%lld" , &a[i]);
        if(a[i] > 0)
            ans += a[i];
    }
    red(i , n , 1){
        if(a[i] < 0){
            ans += a[i] * i ;
        }
    }
    cout << ans << endl;

}

signed main()
{
/*#ifdef ONLINE_JUDGE
#else
    freopen("D:\\c++\\out.txt", "w", stdout);
#endif*/
    //int _ ;cin>>_;while(_--)
        solve() ;
}

树上求和

题意：给出1为根的一棵树，给出初始结点值，q次操作，有两种操作。1、将以x为根的子树都加上y。2、求出以x为根的子树平方和。
输出二操作值。
解法：dfs序区间化，线段树维护，普通和和平方和。

#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef  long long ll ;
#define mod 23333
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 1e6+9;
const int maxn = 1e5+9;
int n , m , p ;
int a[maxn];
int in[maxn] , out[maxn] , cnt , dfn[maxn];
vector<int>g[maxn];
struct tree{
    int l , r , Val , val , lazy;
}tr[maxn<<2];

void dfs(int u , int pre){
    in[u] = ++cnt;
    dfn[cnt] = u ;
    for(auto v : g[u]){
        if(v == pre) continue;
        dfs(v , u);
    }
    out[u] = cnt;
}

void pushup(int root){
    tr[root].val = (tr[root<<1].val + tr[root<<1|1].val)%mod ;
    tr[root].Val = (tr[root<<1].Val + tr[root<<1|1].Val)%mod ;
}

void pushdown(int root){
    int x = tr[root].lazy ;
    tr[root<<1].Val = (tr[root<<1].Val + 2 * x * tr[root<<1].val % mod + (tr[root<<1].r - tr[root<<1].l + 1) * x * x % mod) % mod ;
    tr[root<<1].val = (tr[root<<1].val + (tr[root<<1].r - tr[root<<1].l + 1) * x % mod) % mod ;
    tr[root<<1].lazy = (tr[root<<1].lazy + x) % mod ;

    tr[root<<1|1].Val = (tr[root<<1|1].Val + 2 * x * tr[root<<1|1].val % mod + (tr[root<<1|1].r - tr[root<<1|1].l + 1) * x * x % mod) % mod ;
    tr[root<<1|1].val = (tr[root<<1|1].val + (tr[root<<1|1].r - tr[root<<1|1].l + 1) * x % mod) % mod ;
    tr[root<<1|1].lazy = (tr[root<<1|1].lazy + x) % mod ;

    tr[root].lazy = 0 ;
}

void build(int l , int r , int root){
    tr[root].l = l , tr[root].r = r , tr[root]. lazy = 0 ;
    if(l == r){
        tr[root].val = a[dfn[l]];
        tr[root].Val = tr[root].val * tr[root].val % mod ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(lson);
    build(rson);
    pushup(root);
}


void update(int L , int R , int val , int root){
    if(tr[root].l >= L && tr[root].r <= R){
        tr[root].Val = (tr[root].Val  + 2 * val * tr[root].val % mod  + ((tr[root].r - tr[root].l + 1) * val * val % mod)) % mod ;
        tr[root].val = (tr[root].val + (tr[root].r - tr[root].l + 1) * val % mod) % mod;
        tr[root].lazy = (tr[root].lazy + val) % mod ;
        return ;
    }
    if(tr[root].lazy) pushdown(root);
    int mid = (tr[root].l + tr[root].r) >> 1 ;
    if(mid >= L){
        update(L , R , val , root<<1);
    }
    if(mid < R){
        update(L , R , val , root<<1|1);
    }
    pushup(root);
}

int query(int L , int R , int root){
    int sum = 0 ;
    if(tr[root].l >= L && tr[root].r <= R){
        return tr[root].Val;
    }
    if(tr[root].lazy) pushdown(root);
    int mid = (tr[root].l + tr[root].r) >> 1 ;
    if(mid >= L){
        sum = (sum + query(L , R , root<<1))%mod;
    }
    if(mid < R){
        sum = (sum + query(L , R , root<<1|1))%mod;
    }
    return sum ;
}

void solve(){
    int n , q ;
    scanf("%lld%lld" , &n , &q);
    rep(i , 1 , n){
        scanf("%lld" , &a[i]);
    }
    rep(i , 2 , n){
        int u , v ;
        scanf("%lld%lld" , &u , &v);
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1 , 0);
    build(1 , n , 1);
    while(q--){
        int t , x , y ;
        scanf("%lld%lld" , &t , &x);
        if(t == 1){
            scanf("%lld" , &y);
            update(in[x] , out[x] , y , 1);
        }else{
            cout << query(in[x] , out[x] , 1) << endl;
        }
    }
}

signed main()
{
/*#ifdef ONLINE_JUDGE
#else
    freopen("D:\\c++\\in.txt", "r", stdin);
#endif*/
    //init();
    //int _ ;cin>>_;while(_--)
        solve();
}

算式子

题意：不多说
解法：统计a，考虑右半边式子，枚举a的值域，枚举商，考虑商对连续的x的贡献，利用差分统计。同理统计小于i的数量数组cnt[i]，枚举a值域，枚举商，商为k的a区间的数量对此时的x的贡献。

#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef  long long ll ;
#define mod 23333
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 1e6+9;
const int maxn = 2e6+9;
int cnt[maxn<<1] , ans[maxn<<1];

void solve(){
    int n , m ;
    scanf("%lld%lld" , &n , &m);
    rep(i , 1 , n){
        int x ;
        scanf("%lld" , &x);
        cnt[x]++;
    }
    rep(i , 1 , m){//枚举a[i]值域
        if(cnt[i]){
            for(int k = 1 ; k * i <= m ; k++){//枚举右半边的商
                int l = k * i , r = (k + 1) * i - 1 ;//考虑商会对连续x有贡献
                ans[l] += cnt[i] * k , ans[r+1] -= cnt[i]*k;//差分
            }
        }
    }
    for(int i = 1 ; i <= 2*m ; i++){
        cnt[i] += cnt[i-1] ;//小于i的数量
        ans[i] += ans[i-1] ;
    }
    int kk = 0 ;
    rep(i , 1 , m){
        int sum = ans[i];
        for(int k = 1 ; k * i <= m ; k++){//枚举商
            int l = k * i , r = (k + 1) * i - 1;//商为k的a的区间
            sum += (cnt[r] - cnt[l - 1]) * k ;//商为k的贡献
        }
        kk ^= sum ;
    }
    cout << kk << endl;
}

signed main()
{
/*#ifdef ONLINE_JUDGE
#else
    freopen("D:\\c++\\in.txt", "r", stdin);
#endif*/
    //init();
    //int _ ;cin>>_;while(_--)
        solve();
}