2024.5.16 【就算一次也好，我想在这颗星球上尽情奔跑。】

Thursday 四月初九

数据结构

P4588 TJOI2018 数学计算

//2024.5.16
//by white_ice
//P4588 [TJOI2018] 数学计算
#include<bits/stdc++.h>
using namespace std;
#define itn long long 
#define int long long 
constexpr int oo = 400005;

int n,mod;

itn t;
itn st[oo],f;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> t;

    while (t--){
		cin >> n >> mod;
		for(f=1;f<=n;f<<=1);

		fill(st+1,st+f+n+2,1);

        itn tmp;
		for(int x,k,i=1;i<=n;i++){
			cin >> x >> k;
			if(x==1){
                st[i+f]=k%mod;
                tmp = i+f;
            }
            else{
                st[k+f]=1;
                tmp = k+f;
            }
			while(tmp>>=1)
                st[tmp]=st[tmp<<1]*st[tmp<<1|1]%mod;
			cout << st[1] <<'\n';
		}
	}
    return 0;
}

数学成分很大

题目简单易理解

注意是将x变化，

输出其modM的值

x自身不参与模运算改变

所以维护每个乘数，

对于后面加入的同时修改。

P1486 NOI2004 郁闷的出纳员

//2024.5.16
//by white_ice
//P1486 [NOI2004] 郁闷的出纳员
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define itn long long 
#define int long long 
constexpr int oo = 400005;

int n,minf;
char x;
itn k;

struct nod{
    int v,id;
    nod(int a,itn b){v = a,id = b;}
    bool operator > (nod b)const {return v==b.v?id>b.id:v>b.v;}
};

tree<nod,null_type,greater<nod>,rb_tree_tag,tree_order_statistics_node_update> ned,st;

int out;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n >> minf;
    itn up = 0;
    for (itn i=n;i>0;i--){
        cin >> x;
        cin >> k;
        switch (x){
            case 'I':
                k+=up;
                if (k<minf)
                    break;
                else st.insert(nod(k,i));
                break;
            case 'S':
                up+=k;
                minf +=k; 
                st.split(nod(minf,-1),ned);
                out += ned.size();
                break;
            case 'A':
                up-=k;
                minf -=k;
                break;
            case 'F':
                if (k>st.size())
                    cout << -1 <<'\n';
                else cout << (st.find_by_order(k-1)->v-up) <<'\n';
        }
    }
    cout << out ;
    return 0;
}

标签里写得很清楚

就是一个平衡树的应用

反正我是打不出来这抽象东西

（pb_ds润了）

通过将题目中的加减工资转变为最低工资改变，

巧妙的实现了对树上元素加减的省略。