傳送門

又是一句經(jīng)常見到的話……做完這題對主席樹的理解會更好一些……

這道題把普通的主席樹單點(diǎn)修改區(qū)間查詢改成了區(qū)間修改單點(diǎn)查詢。這個的話我們可以改成差分解決……把一個操作改成兩個，然后把所有操作按照時間進(jìn)行排序。注意這里修改細(xì)節(jié)很多，因?yàn)榭赡茉谝粋€時間上有很多操作，所以我們要先繼承上一個時間點(diǎn)的根的情況，然后對于本時間點(diǎn)的操作，自己繼承自己就可以了。

然后在查詢的時候，這次是直接單點(diǎn)查詢。每次以它的右子樹權(quán)值大小為判定標(biāo)準(zhǔn)進(jìn)行分類遞歸計(jì)算。（具體看代碼）當(dāng)最后只剩下一個優(yōu)先級的時候，他有可能不夠k個，所以要先除以它的個數(shù)再乘以k，即\(sum_p / num_p \times k\)，這樣計(jì)算就可以了。

最后注意優(yōu)先級要離散化。

看一下代碼。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')
#define pr pair<int,int>
#define mp make_pair
#define fi first
#define sc second
using namespace std;
typedef long long ll;
const int M = 200005;
const int N = 1000005;
const int INF = 1000000009;ll read()
{ll ans = 0,op = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') op = -1;ch = getchar();}while(ch >='0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans * op;
}struct node
{int lson,rson;ll sum,v;
}t[N<<4];struct opa
{int tim,rk,val;ll num;bool operator < (const opa &g) const{return tim < g.tim;}
}c[M<<1];int n,m,cnt,root[M],idx;
ll g[M],h[M],x,y,z,pre = 1,a,b,C;void modify(int old,int &p,int l,int r,int val,ll num,int op)
{p = ++idx;t[p].lson = t[old].lson,t[p].rson = t[old].rson;t[p].sum = t[old].sum + num,t[p].v = t[old].v + op;if(l == r) return;int mid = (l+r) >> 1;if(val <= mid) modify(t[old].lson,t[p].lson,l,mid,val,num,op);else modify(t[old].rson,t[p].rson,mid+1,r,val,num,op);
}ll query(int p,int l,int r,ll k)
{if(l == r) return t[p].sum / t[p].v * k;int mid = (l+r) >> 1,now = t[t[p].lson].v;if(k < now) return query(t[p].lson,l,mid,k);else if(k == now) return t[t[p].lson].sum;else return t[t[p].lson].sum + query(t[p].rson,mid+1,r,k - now);
}int main()
{m = read(),n = read();rep(i,1,m){x = read(),y = read(),g[i] = read();c[++cnt].tim = x,c[cnt].val = 1,c[cnt].num = g[i];c[++cnt].tim = y+1,c[cnt].val = -1,c[cnt].num = g[i];}sort(g+1,g+1+m),sort(c+1,c+1+cnt);int tot = unique(g+1,g+1+m) - g - 1;int j = 1;rep(i,1,m+1){root[i] = root[i-1];while(c[j].tim == i && j <= cnt){int cur = lower_bound(g+1,g+1+tot,c[j].num) - g;modify(root[i],root[i],1,tot,cur,c[j].num * c[j].val,c[j].val),j++;}}rep(i,1,n){x = read(),a = read(),b = read(),C = read();ll k = 1 + (a * pre % C + b) % C;if(k > t[root[x]].v) pre = t[root[x]].sum;else pre = query(root[x],1,tot,k);printf("%lld\n",pre);}return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/captain1/p/10098959.html

總結(jié)

以上是生活随笔為你收集整理的CQOI2015 任务查询系统的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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