关于珂学【ODT】
  • 板块学术版
  • 楼主uFTvL9
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/8/23 14:35
  • 上次更新2023/10/27 14:01:48
查看原帖
关于珂学【ODT】
411963
uFTvL9楼主2022/8/23 14:35

如下代吗在输入样例如下时发生运行时错误,然后单步调试跳出cpu窗口和<move.h>。求指出错误。。

1
5
5 3 4 2 1
2 5 2 0

上述样例的解释如下: 进行一组测试,数列长度为5,下一行为数列的元素。 左端点为2,右端点为5,执行操作2(assign),用来推平的数为0

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;

inline int64 fpow(int64 base, int64 ex, int64 mod) {
	base %= mod;
	int64 res = 1;
	while (ex > 0) {
		if (ex & 1) 
			res = res * base % mod;
		base = base * base % mod;
		ex >>= 1;
	}
	return res;
}

/* classes, templates and namespaces */
template<typename any>struct odt { // Old Driver Tree (Chtholly Tree)
	//CORE CODE
	struct odt_node {
		int l, r;
		mutable any data;
		odt_node(int _l, int _r = -1, any _data = 0):l(_l), r(_r), data(_data) {}
		bool operator < (const odt_node &t) const {
			return l < t.l;
		}
	};
	std::set<odt_node> s;
	auto insert(int l, int r = -1, any k = 0) {
		return s.emplace(l, r, k);
	}
	auto begin() {
		return s.begin();
	}
	auto end() {
		return s.end();
	}
	auto split(int pos) {
		auto it = s.lower_bound(pos);
		if(it != s.end() and it->l == pos)return it;
		it--;
		int l = it->l, r = it->r;
		any k = it->data;
		s.erase(it);
		insert(l, pos-1, k);
		return insert(pos, r, k).first;
	}

	//BASE OPERATIONS
	virtual inline int64 add(int l, int r, int delta) {
		int64 res = 0;
		auto it_r = split(r + 1);
		auto it_l = split(l);
		for(; it_l != it_r; ++it_l)
			it_l -> data += delta;
		return res;
	}
	auto assign(int l,int r,any k) {
		auto it_r = split(r + 1), it_l = split(l);
		s.erase(it_l, it_r);
		return insert(l, r, k).first;
	}
	virtual inline int64 kth(int l, int r, int k) {
		auto it_r = split(r + 1);
		auto it_l = split(l);
		vector<pair<int64,int> > vec;
		vec.clear();
		for (; it_l != it_r; ++it_l)
			vec.push_back({it_l->data, it_l->r - it_l->l+1});
		sort(vec.begin(), vec.end());
		for (auto p:vec) {
			k = k - p.second;
			if (k <= 0) return p.first;
		}
		return -1;//k is out of the range
	}
	virtual inline int64 query(int l, int r, int ex, int64 mod) {
		int64 res = 0;
		auto it_r = split(r + 1);
		auto it_l = split(l);
		for(; it_l != it_r; ++it_l)
			res = (res + (it_l->r - it_l->l+1) * fpow(it_l->data, ex, mod) % mod) % mod;
		return res;
	}

	//PERFORMANCE
    inline auto output() {
       for(auto it = s.begin(); it != s.end(); it++) {
            int range = (int)(it->r - it->l+1);
            while(range--)
                cout << (it -> data);
       }
    }

	inline auto performance(int l, int r) {
		auto it_r = split(r + 1);
		auto it_l = split(l);
		for (; it_l != it_r; ++it_l) {
			// Perform Operations here
		}
	}
};

/* AREA LINE */

int T, arr[100000];
int n, lbound, rbound, operat;
odt<int> ODT;

int main() {
    cin >> T >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    while(T--) {
        cin >> lbound >> rbound >> operat;
        if(lbound > rbound)
            lbound ^= rbound ^= lbound ^= rbound;
        int x;
        switch(operat) {
            case 1: {
                //FI >> x;
                cin >> x;
                ODT.add(lbound, rbound, x);
                //ODT.output();
                putchar('\n');
                break;
            }
            case 2: {
                cin >> x;
                ODT.assign(lbound, rbound, x);
                ODT.output();
                putchar('\n');
                break;
            }
            case 3: {
        		cin >> x;
				cout << ODT.kth(lbound, rbound, x);
				putchar('\n');
                break;
            }
            case 4: {
                cin >> x;
				cout << ODT.query(lbound, rbound, x, (int64)(1e9+7));
				putchar('\n');
                break;
            }
        }
    }
    return 0;
}
2022/8/23 14:35
加载中...