顯然是一個比較簡單的離線查詢問題。

本質上是對區(qū)間求集合的問題，按照區(qū)間右端點從小到大對區(qū)間進行排序，然后用一個指針curr表示當前正在考慮區(qū)間的最右側位置，針對排好序區(qū)間[tarl,tarr]，先查看curr是否到達tarr，如果沒到的話，就依次增加curr，并在增加的過程中，不斷維護每種花出現(xiàn)的最晚位置，并把這朵花的魅力值更新進樹狀數(shù)組的相應位置（出現(xiàn)的最晚位置）處。然后就非常的簡單了，要求的區(qū)間[tarl,tarr]的值就是sum(tarr) - sum(tarl-1)

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; struct P {int first;int second;int id;friend bool operator<(P p1,P p2){if(p1.second == p2.second)return p1.first < p2.first;return p1.second < p2.second;} }; const int MAX = 100008; P ps[MAX]; int a[MAX]; vector<int> shop[MAX]; int n,m,q; int maps[MAX]; int ans[MAX]; int bitree[MAX]; inline int lowbit(int x){return x&(-x); } int add(int pos,int val){while(pos <= n){bitree[pos] += val; pos += lowbit(pos);} } int sum(int pos){int ans = 0;while(pos > 0){ans += bitree[pos];pos -= lowbit(pos);}return ans; } int main(){int T;scanf("%d",&T);while(T--){for(int i = 0;i < MAX;i++) shop[i].clear();memset(maps,0,sizeof(maps));memset(ans,0,sizeof(ans));memset(bitree,0,sizeof(bitree));scanf("%d",&m);for(int i = 1;i <= m;i++){scanf("%d",&a[i]);}scanf("%d",&n);for(int i = 1;i <= n;i++){int c;scanf("%d",&c);for(int j = 1;j <= c;j++){int v;scanf("%d",&v);shop[i].push_back(v);}}scanf("%d",&q);for(int i = 1 ;i <= q;i++){int l,r;scanf("%d%d",&l,&r);ps[i].first = l;ps[i].second = r;ps[i].id = i;}sort(ps+1,ps+q+1);int curr = 0;for(int i = 1;i <= q;i++){int tarl = ps[i].first;int tarr = ps[i].second;int id = ps[i].id;if(tarr != curr){while(curr != tarr){curr++;for(int t = 0;t < shop[curr].size();t++){int item = shop[curr][t];if(maps[item]){add(maps[item],-a[item]);}maps[item] = curr;add(maps[item],a[item]);}}}ans[id] = sum(tarr) - sum(tarl-1);}for(int i = 1;i <= q;i++){printf("%d\n",ans[i]);}}return 0; }

總結

以上是生活随笔為你收集整理的北方大学 ACM 多校训练赛 第十五场 买花的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。