做网站 怎么赚钱,山西太原建设银行招聘网站,wordpress 文章置顶不显示,网站开发有哪些方式传送门
题意#xff1a; 思路#xff1a; 题目中(si,ei,pi)(s_i,e_i,p_i)(si,ei,pi)转换成操作即为在[si,ei][s_i,e_i][si,ei]区间内加上pip_ipi的优先级#xff0c;让后查询的话就是查询第xix_ixi秒优先级最小的kik_iki个任务的优先级之和。可知这两个操…传送门
题意 思路 题目中(si,ei,pi)(s_i,e_i,p_i)(si,ei,pi)转换成操作即为在[si,ei][s_i,e_i][si,ei]区间内加上pip_ipi的优先级让后查询的话就是查询第xix_ixi秒优先级最小的kik_iki个任务的优先级之和。可知这两个操作是区间加单点查询。我们通常把这样的操作通过差分的方式转化成单点加区间查询。这样对于每个点都开一颗权值线段树存优先级利用主席树前缀和的性质当前点的权值线段树存的就是当前点包含的优先级。让后直接在权值线段树上二分就好啦。
注意一个时间可能有多个优先级所以lrlrlr的时候返回k∗v[l−1]k*v[l-1]k∗v[l−1]。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#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 pairint,int PII;const int N100010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int root[N],rk[N];
int len,tot,a[N];
vectorintq[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)
{utot; tr[u]tr[pre];tr[u].cntval,tr[u].sum1ll*val*v[pos-1];if(lr) return;int midlr1;if(posmid) change(tr[u].l,tr[pre].l,l,mid,pos,val);else change(tr[u].r,tr[pre].r,mid1,r,pos,val);
}LL query(int u,int l,int r,int k)
{if(lr) return v[l-1]*k; int cnttr[tr[u].l].cnt;int midlr1;if(kcnt) return query(tr[u].l,l,mid,k);else return query(tr[u].r,mid1,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 i1;im;i){int a,b,c; scanf(%d%d%d,a,b,c);q[a].pb(i); q[b1].pb(-i); rk[i]c;v.pb(c);}sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());lenv.size(); LL pre1;for(int i1;in;i){root[i]root[i-1];for(int j0;jq[i].size();j){int xq[i][j];int posfind(rk[abs(x)])1;if(x0) change(root[i],root[i],1,len,pos,1);else change(root[i],root[i],1,len,pos,-1);}}for(int i1;in;i){int x,a,b,c; scanf(%d%d%d%d,x,a,b,c);LL k1(1ll*a*preb)%c;if(tr[root[x]].cntk) pretr[root[x]].sum;else prequery(root[x],1,len,k);printf(%lld\n,pre);}return 0;
}
/**/
