4
资深天翼
为什么爆零了？
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
struct Tree{
int l,r;
long long sum,size;
}tree[int(1e7+10)];
const int maxn=301000;
int a[maxn],s[maxn],t[maxn],times[maxn];
vector<int>G[maxn];
int tot=0;
inline int build(int l,int r)
{
tot++;
int num=tot;
int mid=(l+r)/2;
if(l<r)
{
tree[num].l=build(l,mid);
tree[num].r=build(mid+1,r);
}
return num;
}
inline int update(int pre,int l,int r,int k,int k2)
{
int num=++tot;
tree[num].l=tree[pre].l;
tree[num].r=tree[pre].r;
tree[num].size=tree[pre].size+k2;
tree[num].sum=tree[pre].sum+k;
int mid=(l+r)/2;
if(l<r)
{
if(max(k,-k)<=mid)
tree[num].l=update(tree[pre].l,l,mid,k,k2);
else
tree[num].r=update(tree[pre].r,mid+1,r,k,k2);
}
return num;
}
long long query(int x,int l,int r,int k)
{
if(l==r) return (long long)l*k;
int mid=(l+r)/2;
if(tree[tree[x].l].size>=k)
return query(tree[x].l,l,mid,k);
else
return tree[tree[x].l].sum+query(tree[x].r,mid+1,r,k-tree[tree[x].l].size);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
scanf("%d%d%d",&s[i],&t[i],&a[i]);
G[s[i]].push_back(a[i]);
G[t[i]+1].push_back(-a[i]);
}
times[0]=build(1,n);
for(int i=1; i<=n; i++)
{
times[i]=times[i-1];
for(int j=0; j<G[i].size(); j++)
{
times[i]=update(times[i],1,n,G[i][j],G[i][j]>0?1:-1);
}
}
long long last=1;
for(int i=1; i<=m; i++)
{
long long x,a,b,c;
scanf("%lld%lld%lld%lld",&x,&a,&b,&c);
long long k=1+(a*last+b)%c;
long long t=0;
if(k>=tree[times[x]].size) t=tree[times[x]].sum;
else t=query(times[x],1,n,k);
printf("%lld\n",(last=t));
}
return 0;
}
陆麟瑞在2019-03-09 12:31:00追加了内容
是洛谷的3168,不是CDT的
1
资深天翼
手动
@牛天淏
滑稽
1
中级守护
我是你粉丝啊啊啊啊 你写的都是对的加油( •̀ ω •́ )y
1
修练者
应该不会吧，再试试！
加油
顺便问一下3908，酷町堂
0
新手天翼
我不太清楚 但以我多次错误的经验来看 初始值 max要赋值与数组[1]；
min也赋值与数组[1]；
一般都是赋值错误 你找找吧
王子逸在2020-06-01 19:04:00追加了内容
你也可以输出过程 这样就知道哪的环节出问题了！！！
0
新手天翼
shui
0
高级光能
不会+1
0
中级天翼
I don't know!
0
资深光能
666
0
初级天翼
666
0
资深光能
未学到
0
资深守护
666
0
被禁言
中级光能
奥力给！！！
0
资深光能
?
0
高级启示者
吓到我了，我还以为陆大佬回归了，结果一看时间。。。
绝对有人挖坟。。。
0
资深光能
66^-^66
0
新手天翼
两年前贴在第一面，我刚发的贴没人回答。。。
0
中级光能
大佬回归了？
李玥仑在2021-05-04 23:53:17追加了内容
看了一眼时间
( Ĭ ^ Ĭ )
我真的是傻了吧唧的
0
高级天翼
额………………………………
0
资深天翼
1
0
资深天翼
别蹭帖了（除了本帖）
0
缔造者之神
太厉害了
0
资深光能
wawen
0
被禁言
中级光能
题目内容是什么
0
初级天翼
不会啊
0
高级启示者
陆大佬回来了？
————
汗，弄错了
2年前。。。
0
缔造者之神
挖
0
初级启示者
额。。。。
0
中级天翼
666
0
初级天翼
这题不是记忆化吗？
貌似拓扑排序也能做，不过我记忆化搜索AC了
