珂朵莉树学习

题目

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #include 
#include 
#include 
#include 
#include 
using namespace std;//void rfIO()
//{
//	FILE *stream1;
//	freopen_s(&stream1,"in.txt", "r", stdin);
//	freopen_s(&stream1,"out.txt", "w", stdout);
//}
//
inline void read(int &x){x = 0;char ch = getchar(); int f = 1;while (!isdigit(ch) && ch^'-') ch = getchar();if (ch == '-') f = -1, ch = getchar();while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();x *= f;
}
static auto speedup = [](){ios::sync_with_stdio(false); cin.tie(); cout.tie(); return nullptr; }();#define It set<Node>::iteratorclass Prime{
public:void Init(int len){bo.assign(len + 1, true);int s = sqrt(len);for (int i = 2; i <= s; i++){if (!bo[i])continue;for (int j = i * i; j <= len; j += i){bo[j] = false;}}}bool IsPrime(int x){return bo[x];}
public:vector<bool> bo;
}p;struct Node{int l, r;mutable int val;bool operator<(const Node &input)const{return l < input.l;}
};set<Node> mset;It split(int pos){It it = mset.lower_bound(Node{pos,0,0});if (it != mset.end() && it->l == pos) return it;it--;int l = it->l, r = it->r, val = it->val;mset.erase(it);mset.insert(Node{ l, pos - 1, val });return mset.insert(Node{ pos, r, val }).first;
}void merge(int l,int r,int val){It  itr = split(r + 1), itl = split(l);mset.erase(itl, itr);mset.insert(Node{ l, r, val });
}int query(int l, int r){int ans = 0;It itr = split(r + 1), it = split(l);for (; it != itr; it++){if (p.IsPrime(it->val)){ans += it->r - it->l + 1;}}return ans;
}int t,n,m;
int main(){p.Init(1e6 + 7);cin >> t;for (int i = 1; i <= t; i++){cin >> n >> m;mset.clear();int tmp;for (int i = 1; i <= n; i++){cin >> tmp;mset.insert(Node{ i, i, tmp });}cout << "Case " << i << ":" << endl;while (m--){int opt, x, y, v;cin >> opt >> x >> y;if (opt == 0){cin >> v;merge(x, y, v);}else{cout << query(x, y) << endl;}}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！