CQOI2015 任务查询系统

传送门

又是一句经常见到的话……做完这题对主席树的理解会更好一些……

这道题把普通的主席树单点修改区间查询改成了区间修改单点查询。这个的话我们可以改成差分解决……把一个操作改成两个，然后把所有操作按照时间进行排序。注意这里修改细节很多，因为可能在一个时间上有很多操作，所以我们要先继承上一个时间点的根的情况，然后对于本时间点的操作，自己继承自己就可以了。

然后在查询的时候，这次是直接单点查询。每次以它的右子树权值大小为判定标准进行分类递归计算。（具体看代码）当最后只剩下一个优先级的时候，他有可能不够k个，所以要先除以它的个数再乘以k，即\(sum_p / num_p \times k\)，这样计算就可以了。

最后注意优先级要离散化。

看一下代码。

#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;
}