傳送門

題意：

思路： 題目中$(s_i,e_i,p_i)$轉換成操作即為在$[s_i,e_i]$區間內加上$p_i$的優先級，讓后查詢的話就是查詢第$x_i$秒優先級最小的$k_i$個任務的優先級之和。可知這兩個操作是區間加，單點查詢。我們通常把這樣的操作通過差分的方式轉化成單點加，區間查詢。這樣對于每個點都開一顆權值線段樹存優先級，利用主席樹前綴和的性質，當前點的權值線段樹存的就是當前點包含的優先級。讓后直接在權值線段樹上二分就好啦。

注意一個時間可能有多個優先級，所以$l==r$的時候返回$k?v[l?1]$。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; int root[N],rk[N]; int len,tot,a[N]; vector<int>q[N],v; struct Node {int l,r;int cnt;LL sum; }tr[N*40];int find(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin(); }void change(int &u,int pre,int l,int r,int pos,int val) {u=++tot; tr[u]=tr[pre];tr[u].cnt+=val,tr[u].sum+=1ll*val*v[pos-1];if(l==r) return;int mid=l+r>>1;if(pos<=mid) change(tr[u].l,tr[pre].l,l,mid,pos,val);else change(tr[u].r,tr[pre].r,mid+1,r,pos,val); }LL query(int u,int l,int r,int k) {if(l==r) return v[l-1]*k; int cnt=tr[tr[u].l].cnt;int mid=l+r>>1;if(k<=cnt) return query(tr[u].l,l,mid,k);else return query(tr[u].r,mid+1,r,k-cnt)+tr[tr[u].l].sum; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d%d",&m,&n);for(int i=1;i<=m;i++){int a,b,c; scanf("%d%d%d",&a,&b,&c);q[a].pb(i); q[b+1].pb(-i); rk[i]=c;v.pb(c);}sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());len=v.size(); LL pre=1;for(int i=1;i<=n;i++){root[i]=root[i-1];for(int j=0;j<q[i].size();j++){int x=q[i][j];int pos=find(rk[abs(x)])+1;if(x>0) change(root[i],root[i],1,len,pos,1);else change(root[i],root[i],1,len,pos,-1);}}for(int i=1;i<=n;i++){int x,a,b,c; scanf("%d%d%d%d",&x,&a,&b,&c);LL k=1+(1ll*a*pre+b)%c;if(tr[root[x]].cnt<k) pre=tr[root[x]].sum;else pre=query(root[x],1,len,k);printf("%lld\n",pre);}return 0; } /**/

總結

以上是生活随笔為你收集整理的P3168 [CQOI2015]任务查询系统 主席树 + 差分的全部內容，希望文章能夠幫你解決所遇到的問題。

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