题解

这真有紫吗。

直接解有点困难，考虑转化。

我们可以求出每块木板被哪颗子弹击碎。问题可以转化成：

给定一个长度为 $m$ 的数组 $A$，$n$ 次查询，每次给出 $l,r$，查询满足 $\sum_{i=1}^k [l\le A_k\le r]$ 的最小的 $k$。

注意到这个查询是可减的，即可以转化成 $(\sum_{i=1}^k [A_i\le r])-(\sum_{i=1}^k [A_i\lt l])$。

我们可以开 $2\times 10^5$ 颗线段树，第 $i$ 颗线段树下标 $j$ 记录 $A_j$ 是否小于等于 $i$。显然可以递推建主席树。查询直接第 $r$ 颗树减第 $l-1$ 颗树，线段树二分即可。

namespace cjdst{
    template <typename T>
	class HJT_Segtree{
		class node{
			public:

			T val;
			int left, right;
			node *lson, *rson;
			node(){
				val = left = right = 0;
				lson = rson = 0;
			}
		};
		std::vector <node*> roots;
		int len;

		void push_up(node *cur){
			cur -> val = cur -> lson -> val + cur -> rson -> val;
		}

		void build(node *cur, int l, int r){
			cur -> left = l;
			cur -> right = r;
			if(l == r){
				cur -> val = 0;
				return;
			}
			int mid = (l + r) >> 1;
			node *ls = new node, *rs = new node;
			cur -> lson = ls;
			cur -> rson = rs;
			build(ls, l, mid);
			build(rs, mid + 1, r);
			push_up(cur);
		}

		void _build_new(node *cur, node *pre, int idx){
			int l = pre -> left;
			int r = pre -> right;
			cur -> left = l;
			cur -> right = r;
			if(l == r){
				cur -> val = 1;
				return;
			}
			int mid = (l + r) >> 1;
			node *ls, *rs;
			if(idx <= mid){
				ls = new node, rs = pre -> rson;
				cur -> lson = ls, cur -> rson = rs;
				_build_new(ls, pre -> lson, idx);
			}else{
				ls = pre -> lson, rs = new node;
				cur -> lson = ls, cur -> rson = rs;
				_build_new(rs, pre -> rson, idx);
			}
			push_up(cur);
		}

		T _query(node *cur, node *pre, int k){
			if(cur -> val < k) return -1;
			if(cur -> left == cur -> right){
				return cur -> left;
			}
			int tmp = cur -> lson -> val - pre -> lson -> val;
			if(k <= tmp) return _query(cur -> lson, pre -> lson, k);
			else return _query(cur -> rson, pre -> rson, k - tmp);
		}

		public:

		HJT_Segtree(){len = 0;}
		HJT_Segtree(int n){
			node *root = new node;
			build(root, 1, n);
			roots.push_back(root);
		}
		
		int last_root(){
			return roots.size() - 1;
		}

		void build_new(int pre, int idx){
			node *cur = new node;
			_build_new(cur, roots[pre], idx);
			roots.push_back(cur);
		}

		T query(int cur, int pre, int k){
			return _query(roots[cur], roots[pre], k);
		}
	};

	void solve(){
		int n, m;
		std::cin >> m >> n;
		std::vector <int> a(n + 5);
		std::vector <std::vector <int>> b(200005);
		std::vector <int> x(m + 5), y(m + 5), s(m + 5);
		std::vector <int> ans(n + 5);
		for(int i = 1; i <= m; i++){
			std::cin >> x[i] >> y[i] >> s[i];
		}
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			b[a[i]].push_back(i);
		}
		HJT_Segtree <int> tr(n + 5);
		std::vector <int> roots(200005);
		for(int i = 1; i <= 200000; i++){
			for(int j:b[i]){
				tr.build_new(tr.last_root(), j);
			}
			roots[i] = tr.last_root();
		}
		for(int i = 1; i <= m; i++){
			int cur = tr.query(roots[y[i]], roots[x[i] - 1], s[i]);
			if(cur != -1) ans[cur]++;
		}
		for(int i = 1; i <= n; i++){
			std::cout << ans[i] << '\n';
		}
	}
}

时间复杂度 $O(n\log n)$。但怎么耗时比隔壁双 log 解法还要高呢，先天大常数圣体发力了（（（