```cpp
#include<bits/stdc++.h>
#define ll unsigned long long
#define maxn 301000
#define ls rt<<1,s,mid
#define rs rt<<1|1,mid+1,t
using namespace std;
int tr[maxn<<2],n,t1,t2,t3,t4,m;
struct lazy
{
ll s1,d;
int is;
}la[maxn<<2];
ll get_sn(int s,int t,int s1,int d)
{
int len=t-s+1;
int sn=(s1+s1+(len-1)*d)*len/2;
return sn;
}
void pushdown(int rt,int s,int t)
{
if(la[rt].is)
{
la[rt<<1].is=1;
la[rt<<1|1].is=1;
int mid=(t+s)>>1;
la[rt<<1].s1+=la[rt].s1;
la[rt<<1|1].s1+=la[rt].s1+la[rt].d*(mid-s+1);
la[rt<<1].d+=la[rt].d;
la[rt<<1|1].d+=la[rt].d;
tr[rt<<1]+=get_sn(s,mid,la[rt<<1].s1,la[rt<<1].d);
tr[rt<<1|1]+=get_sn(mid+1,t,la[rt<<1|1].s1,la[rt<<1|1].d);
la[rt].is=0;
}
}
ll query(int rt,int s,int t,int id)
{
if(s==t&&s==id)
return tr[rt];
pushdown(rt,s,t);
int mid=(s+t)>>1;
if(id<=mid)return query(ls,id);
else return query(rs,id);
}
void update(int rt,int s,int t,int ss,int tt,int s1,int d)
{
if(t<ss||tt<s)
return;
if(ss<=s&&t<=tt)
{
la[rt].s1=s1;
la[rt].d=d;
la[rt].is=1;
tr[rt]+=get_sn(s,t,s1,d);
return;
}
int mid=(t+s)>>1;
pushdown(rt,s,t);
update(ls,ss,tt,s1,d);
update(rs,ss,tt,s1+d*(mid-s+1),d);
tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
int main()
{
// scanf("%d",&n,&m);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
// scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
cin>>t1>>t2>>t3>>t4;
int a=(t4-t3)/(t2-t1);
update(1,1,n,t1,t2,t3,a);
}
int ans=query(1,1,n,1);
// cout<<ans<<" ";
int ans1=0;
for(int i=2;i<=n;i++)
{
int t=query(1,1,n,i);
// cout<<t<<" ";
ans1=max(ans1,t);
ans^=t;
}
cout<<ans<<" "<<ans1;
return 0;
}
```
by 随心唯爱 @ 2018-02-16 09:39:59
n最大为10^7，线段树维护区间加等差数列好像不行吧........
by wh_ZH @ 2018-02-16 10:18:51
复杂度带log很难卡过吧，正解是O(n+m)的
by orangebird @ 2018-02-17 00:17:29
差分多好啊，又快思路又清晰
by kl膜法59改 @ 2018-09-27 17:17:16
你确定没有MLE？
by zi小眼聚光 @ 2019-03-15 19:14:35