USACO填坑计划
maya终于有填坑计划了
主要是最近不知道做什么题好
看到*利去年同期的刷题节奏感觉很带感的样子于是跟着进度做一做好了。虽然那种效率肯定是跟不上的
话说Silver的题好像确实都不是很难的样子反正按记录一路扫过去好了
[upd 9.11] 差不多都搞完了，刷水真是刷的人好虚。里面有的比较卡的题目要不就是比较神的贪心要不就是复杂度不科学但还是能过的题。
BZOJ1613 直接DP
BZOJ1622 我反正是乱搞，先建出一棵trie数然后每次维护一些还可以往下扩展的节点。但是复杂度算起来并不很科学，不过还是过了。
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 3050
#define M 105
queue <int> a[N],empty;
int n,m,s[N],ne[N][M],li[N],ans,len,st=1,sg[N];
char b[N],qu[N][N];
int main()
{
cin >>n>>m;
for (int i=1;i<=n;i++)
scanf("%s",qu[i]);
for (int i=1;i<=m;i++)
{
scanf("%s",b);len=strlen(b);
for (int j=0;j<len;j++)
if (b[j]<'a') b[j]=b[j]-'A'+'a';
int now=1;
for (int j=0;j<len;j++)
if (!ne[now][b[j]-'a'])
ne[now][b[j]-'a']=++st,now=st;else
now=ne[now][b[j]-'a'];
s[now]++;
}
for (int i=1;i<=n;i++)
{
len=strlen(qu[i]);ans=0;
for (int j=0;j<len;j++)
if (qu[i][j]<'a') qu[i][j]=qu[i][j]-'A'+'a';
for (int j=0;j<26;j++)
{
a[j]=empty;
if (ne[1][j]) a[j].push(1);
}
for (int j=0;j<len;j++)
{
int k=qu[i][j]-'a',ss=0;
while (a[k].size())
li[++ss]=a[k].front(),a[k].pop();
while (ss--)
{
int l=ne[li[ss+1]][k];
for (int q=0;q<26;q++)
if (ne[l][q])
a[q].push(l);
ans+=s[l];
}
}
printf("%d\n",ans);
}
return 0;
}
BZOJ1623 一个比较显然的贪心
BZOJ1628 用个set维护下现在还存在的矩形的高度然后从左往右扫一遍就好了
BZOJ1633 也是DP
BZOJ1634 按照Di/Ti排个序就是顺序，至于证明可以考虑交换两个相邻的牛的顺序对答案的影响
BZOJ1635 Get差分序列，感觉神神的，贪心也神神的。
BZOJ1636 直接倍增搞
BZOJ1637 值化成1和-1前缀和一下然后排个序求出同一前缀和的最大区间最后倍增统计答案
BZOJ1638 两次拓扑排序
BZOJ1639 二分答案
BZOJ1640 贪心，两端不同就取小的，否则往中间一直找不同的。这样可以搞成O(n)的。有人用后缀数组真是不明觉厉，不过本质还是一样的。
BZOJ1641 Floyd
BZOJ1642 排序扫一遍
BZOJ1643 DP
BZOJ1644 BFS
BZOJ1645 刚看题还以为是扫描线，结果sort一遍扫一遍就好了
BZOJ1646 BFS
BZOJ1648 BFS
BZOJ1649 背包
BZOJ1650 二分答案+贪心
BZOJ1651 二分答案
BZOJ1652 DP
BZOJ1653 爆搜
BZOJ1654 Tarjan求LCC
BZOJ1655 高J度+DP
BZOJ1657 单调队列
BZOJ1658 贪心+差分序列
就是方向向左的路线记为1，否则记为-1，然后每段区间的权值和的绝对值*路线长度的和就是答案，脑补感觉还是比较正确
BZOJ1660 单调队列
BZOJ1661 爆搜
BZOJ1662 数位DP
BZOJ1663 DP
BZOJ1664 排序乱搞
BZOJ1665 暴力建图BFS
BZOJ1666 高J度
BZOJ1668 DP
BZOJ1669 n^2 LIS都可以过
BZOJ1671 BFS
BZOJ1672 排序后贪心
BZOJ1673 因为个数不会太多所以直接爆搜
BZOJ1674 直接建图BFS
BZOJ1676 直接爆搞
BZOJ1677 DP
BZOJ1679 排序乱搞
BZOJ1680 贪心
BZOJ1681 最短路
BZOJ1682 最小生成树
BZOJ1683 同1628
BZOJ1684 枚举分母，则分子是可以限制在一定范围内的
BZOJ1685 有个神神的贪心是每次先把大的尽可能拿掉，最后补个最小的
BZOJ1688 并查集
BZOJ1689 贪心
BZOJ2014 贪心
BZOJ2015 SPFA
BZOJ2016 二分答案
BZOJ2019 SPFA
BZOJ2020 贪心
BZOJ2021 背包
BZOJ2023 DP
BZOJ2101 DP
BZOJ2102 爆搜
BZOJ3016 往前往后扫一遍
BZOJ3017 DP
BZOJ3018 跑n^2次SPFA
BZOJ3296 并查集
BZOJ3297 DP
BZOJ3298 打表找规律发现每条y=x+k总会有一个后手必胜点，然后就可以先把这些点预处理出来最后判断就好了
BZOJ3300 栈
BZOJ3301 DP
BZOJ3389 贪心
BZOJ3390 最小生成树
BZOJ3391 树的重心
BZOJ3392 BFS
BZOJ3396 Dinic
BZOJ3399 贪心
BZOJ3400 DP
BZOJ3402 BFS
BZOJ3403 队列
BZOJ3404 预处理
BZOJ3410 贪心
BZOJ3432 二分答案
BZOJ3433 好神的贪心，是每次看能不能填右端点大的，不能就填右端点较小的。
BZOJ3479 最小生成树
BZOJ3480 预处理背包一下求出每个大小的最小值，直接从左往右扫一遍就好了
BZOJ3538 三次SPFA
BZOJ3540 前缀和+归并排序
WC2013 糖果公园
早有耳闻的sxbk题
一直以为带修改树上莫队一定有着很高的技巧
于是去膜了一发题解
才发现这道题主要是在排序上面加特技
考虑将询问分块，然后与普通莫队不同的地方是我们将询问按照左端点的块编号、右端点的块编号、在第几次修改之后三个关键字排序。
这样在n^(2/3)个块区间里面的修改因为时间有序了所以是O(n)的。然后询问的话反正区间内的修改是n^(2/3)的，区间开头的询问也可以暴力O(n)搞。
所以时间的操作是O(n^(5/3))的，而其他树上莫队的部分也是O(n^(5/3))
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define M 400050
#define ll long long
#define eps 1e-5
int c[N*2][2],fi[N],fa[N],sg[N][2],rt,n,m,Sign[M],t[M];
int li[N],cl[N],mo[N][3],qu[N][2],ss,st,p,cnt[N];
int now,nt[M];ll ans[N],Ans,tot[N];
struct Color
{
ll wi[N],v[N],s[N];
inline void Insert(int x)
{Ans+=wi[++s[x]]*v[x];}
inline void Delete(int x)
{Ans-=wi[s[x]--]*v[x];}
} Aha;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
nt[sg[x][0]=++st]=x;tot[x]=2;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
{
if (nt[st]!=x) nt[++st]=x,tot[x]++;
fa[c[i][0]]=x,DFS(c[i][0]);
}
nt[sg[x][1]=++st]=x;
}
inline bool cmp(int x,int y)
{return Sign[qu[x][0]]<Sign[qu[y][0]]||
(Sign[qu[x][0]]==Sign[qu[y][0]]&&(Sign[qu[x][1]]<
Sign[qu[y][1]]||(Sign[qu[x][1]]==Sign[qu[y][1]]&&
t[x]<t[y])));}
void Pretreat()
{
DFS(1);
rt=pow(st,2.0/3.0)+eps;
for (int i=1;i<=st;i++) Sign[i]=(i-1)/rt;
for (int i=1;i<=p;i++)
{
if (sg[qu[i][1]][0]<sg[qu[i][0]][0])
swap(qu[i][1],qu[i][0]);
qu[i][0]=sg[qu[i][0]][sg[qu[i][0]][1]<sg[qu[i][1]][1]];
qu[li[i]=i][1]=sg[qu[i][1]][0];
}
for (int i=1;i<=now;i++)
mo[i][1]=cl[mo[i][0]],cl[mo[i][0]]=mo[i][2];
for (int i=now;i>=1;i--)
cl[mo[i][0]]=mo[i][1];
sort(li+1,li+p+1,cmp);
}
inline void Move(int x,int y)
{
bool r=(cnt[mo[x][0]]<tot[mo[x][0]])
&&(cnt[mo[x][0]]>0);
if (r) Aha.Delete(mo[x][y]);
cl[mo[x][0]]=mo[x][3-y];
if (r) Aha.Insert(mo[x][3-y]);
}
inline void Modify(int x,int y)
{
cnt[x]+=y;
if (!cnt[x]||cnt[x]==tot[x]) Aha.Delete(cl[x]); else
if (cnt[x]-y==0||cnt[x]-y==tot[x]) Aha.Insert(cl[x]);
}
void Solve()
{
int le=1,ri=0;now=0;
for (int i=1;i<=p;i++)
{
int k=qu[li[i]][0],l=qu[li[i]][1];
for (;le<k;le++) Modify(nt[le],-1);
for (;le>k;) Modify(nt[--le],1);
for (;ri>l;ri--) Modify(nt[ri],-1);
for (;ri<l;) Modify(nt[++ri],1);
for (;now<t[li[i]];) Move(++now,1);
for (;now>t[li[i]];) Move(now--,2);
ans[li[i]]=Ans;
}
return;
}
int main()
{
n=Read();m=Read();p=Read();
for (int i=1;i<=m;i++) Aha.v[i]=Read();
for (int i=1;i<=n;i++) Aha.wi[i]=Read();
for (int i=1;i<n;i++)
Line(Read(),Read());
for (int i=1;i<=n;i++) cl[i]=Read();
int o=p;p=0;
while (o--)
if (Read())
qu[++p][0]=Read(),qu[p][1]=Read(),t[p]=now;else
mo[++now][0]=Read(),mo[now][2]=Read();
Pretreat();
Solve();
for (int i=1;i<=p;i++)
printf("%lld\n",ans[i]);
return 0;
}
SPOJ QTREE5
话说这博客我自己都有的时候上不去不知道是smg
题面：给n（n<=10w）个点，一开始全部都是黑色的，有（好像是）10w个操作，每次改变一个节点的颜色（黑白转换）或者询问一个点与其最近白点的距离（如果没有就是-1）
这题比QTREE4（BZOJ 1095）好写到不知道哪里去了，反正我是用了树链剖分
就是每个节点把其所有轻儿子的子树的节点的白点距离用set存起来，每次变颜色就只会改变log n个，然后弄两棵线段树存下一条重链上所有点set的顶部的值+其到链首/链尾的距离，所以也可以直接查询。
动态树分治的思路跟QTREE4差不多，只不过查询那个点到重心的距离+重心的其它子树的最小值的和的最小值，反正也是用几个set搞一下什么的，但是感觉麻烦些。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
multiset <int> a[N];
set <int> :: iterator it;
int fa[N],c[N*2][2],fi[N],sg[N],st=0,ss=1,n,m;
int h[N][3],rf[N],dep[N],tot,sum[N];bool b[N];
struct Segment_Tree
{
int a[N*3];
void Set_up(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
a[z]=INF;
if (x!=y) Set_up(x,i,j),Set_up(i+1,y,j+1);
}
void Ins(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;
if (x==y) {a[z]=p;return;}
if (o<=i) Ins(x,i,j,o,p);else
Ins(i+1,y,j+1,o,p);
a[z]=min(a[j],a[j+1]);
}
int Que(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1,k=INF;
if (x==o&&y==p) return a[z];
if (o<=i) k=Que(x,i,j,o,min(p,i));
if (p>i) k=min(k,Que(i+1,y,j+1,max(o,i+1),p));
return k;
}
void Insert(int x,int y)
{Ins(1,n,1,x,y);}
int Query(int x,int y)
{return Que(1,n,1,x,y);}
} mi[2];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
h[x][0]=h[fa[x]][0]+1;sum[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
fa[c[i][0]]=x,DFS(c[i][0]),sum[x]+=sum[c[i][0]];
return;
}
int DSF(int x,int y)
{
int k=0;sg[x]=++st;
rf[x]=y;h[x][1]=h[x][0]-h[y][0];
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&sum[c[i][0]]>sum[k])
k=c[i][0];
dep[x]=!k?x:DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&c[i][0]!=k)
DSF(c[i][0],c[i][0]);
h[x][2]=h[dep[x]][0]-h[x][0];
return dep[x];
}
void Insert(int x)
{
int s=0;
while (x)
{
it=a[x].begin();
int k=it==a[x].end()?INF:*it;
a[x].insert(s);
if (s<k)
mi[0].Insert(sg[x],s+h[x][1]),
mi[1].Insert(sg[x],s+h[x][2]);
s+=h[x][0]-h[fa[rf[x]]][0];x=fa[rf[x]];
}
}
void Delete(int x)
{
int s=0;
while (x)
{
it=a[x].begin();int k=*it;
it=a[x].lower_bound(s);a[x].erase(it);
it=a[x].begin();int l=it==a[x].end()?INF:*it;
if (k!=l)
mi[0].Insert(sg[x],l==INF?INF:l+h[x][1]),
mi[1].Insert(sg[x],l==INF?INF:l+h[x][2]);
s+=h[x][0]-h[fa[rf[x]]][0];x=fa[rf[x]];
}
}
int Query(int x)
{
int s=0,ans=INF;
while (x)
{
ans=min(ans,s+mi[0].Query(sg[x],sg[dep[x]])
-h[x][0]+h[rf[x]][0]);
ans=min(ans,s+mi[1].Query(sg[rf[x]],sg[x])
-h[dep[x]][0]+h[x][0]);
s+=h[x][0]-h[fa[rf[x]]][0];x=fa[rf[x]];
}
return ans;
}
int main()
{
n=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
DFS(1);DSF(1,1);
mi[0].Set_up(1,n,1);mi[1].Set_up(1,n,1);
m=Read();
while (m--)
if (!Read())
{
int k=Read();b[k]=!b[k];
if (!b[k]) Delete(k),tot--;else Insert(k),tot++;
} else
{
int k=Read();
printf("%d\n",tot?Query(k):-1);
}
return 0;
}
BZOJ 1095
这题做的我真是感动
有线段树和动态树分治的做法（话说第一次看到我还以为是动态树的分治【捂脸*ei】），我在考场上面写的是后者，但是当时打错了一个变量，然后爆零了，改完就A了。但是那个题好像数据比较特殊，所以那题代码蒯过来是wa的。于是这种喜闻乐见的东西我重写了一遍，调了一上午，欲仙欲死。
裸题，首先点分治一下，然后用2n个set保存每个分治的重心和它的儿子们的答案，然后对于每次操作就直接添加删除什么的就好了。
当然用优先队列是要比set快一些的。
代码高能
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
struct Set
{
multiset <int> li;
set <int> :: iterator it;
inline int Sum()
{return li.size();}
inline void Ins(int x)
{li.insert(-x);}
inline void Del(int x)
{it=li.lower_bound(-x);li.erase(it);}
inline int Top()
{it=li.begin();return it!=li.end()?-*it:0;}
inline int Sec()
{it=li.begin();return Sum()<2?0:Top()-*(++it);}
} a[N*2];
int h[N][20],s[N],n,m,c[N*2][2],fi[N],tot,la[N];
int ss=1,st=0,li[N],sum[N][2],sub[N][20];
int sg[N],rt[N][20],cnt;bool t[N];char b[20];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
int BFS(int x)
{
int le=1,ri=1;
li[1]=x;sum[x][1]=++tot;sum[x][0]=la[x]=0;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!s[c[i][0]]&&sum[c[i][0]][1]!=tot)
sum[c[i][0]][1]=tot,sum[c[i][0]][0]=0,
li[++ri]=c[i][0],la[c[i][0]]=li[le];
for (--le;le;le--)
sum[la[li[le]]][0]+=++sum[li[le]][0];
return ri;
}
void BSF(int x,int y)
{
int le=1,ri=1;
li[1]=x;sum[x][1]=++tot;h[x][y]=0;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!s[c[i][0]]&&sum[c[i][0]][1]!=tot)
sum[c[i][0]][1]=tot,h[c[i][0]][y]=h[li[le]][y]+1,
li[++ri]=c[i][0];
return;
}
int Find(int x,int y)
{
while (1)
{
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=la[x]&&sum[c[i][0]][1]==tot&&
sum[c[i][0]][0]>y/2)
{x=-c[i][0];break;}
if (x>0) return x;else x=-x;
}
}
void Set_up(int x,int y)
{
int k=BFS(x),root=Find(x,k),le=2;BSF(root,y);
a[sg[root]=sub[root][s[root]=y]=++st].Ins(0);
if (k==1) {a[0].Ins(0);return;}
for (int i=fi[root];i;i=c[i][1])
if (!s[c[i][0]])
a[sub[c[i][0]][y]=++st].Ins(1),
rt[c[i][0]][y]=sg[root];
for (;le<=k;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!s[c[i][0]]&&!sub[c[i][0]][y])
a[sub[c[i][0]][y]=sub[li[le]][y]].
Ins(h[c[i][0]][y]),rt[c[i][0]][y]=sg[root];
for (int i=fi[root];i;i=c[i][1])
if (!s[c[i][0]])
a[sg[root]].Ins(a[sub[c[i][0]][y]].Top());
a[0].Ins(a[sg[root]].Sec());
for (int i=fi[root];i;i=c[i][1])
if (!s[c[i][0]]) Set_up(c[i][0],y+1);
return;
}
void Insert(int x)
{
for (int i=1;i<s[x];i++)
{
int ans=a[sub[x][i]].Top(),Ans,S;
a[sub[x][i]].Ins(h[x][i]);
if (h[x][i]<=ans) continue;
Ans=a[rt[x][i]].Sec();
if (a[sub[x][i]].Sum()>1) a[rt[x][i]].Del(ans);
a[rt[x][i]].Ins(a[sub[x][i]].Top());
S=a[rt[x][i]].Sec();
if (S!=Ans)
a[0].Del(Ans),a[0].Ins(S);
}
a[sg[x]].Ins(0);
if (a[sg[x]].Sum()==2) a[0].Ins(a[sg[x]].Sec());
}
void Delete(int x)
{
for (int i=1;i<s[x];i++)
{
int ans=a[sub[x][i]].Top(),Ans,S;
a[sub[x][i]].Del(h[x][i]);
if (h[x][i]<ans) continue;
Ans=a[rt[x][i]].Sec();
a[rt[x][i]].Del(ans);
if (a[sub[x][i]].Sum())
a[rt[x][i]].Ins(a[sub[x][i]].Top());
S=a[rt[x][i]].Sec();
if (S!=Ans)
a[0].Del(Ans),a[0].Ins(S);
}
int Ans=a[sg[x]].Sec();
a[sg[x]].Del(0);
if (a[sg[x]].Sum()==1) a[0].Del(Ans);
}
int main()
{
n=cnt=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
Set_up(1,1);m=Read();
while (m--)
{
scanf("%s",b);
if (b[0]=='G')
printf("%d\n",cnt<=1?cnt-1:a[0].Top());else
{
int k=Read();
if (t[k]) cnt++,Insert(k);else
cnt--,Delete(k);
t[k]=!t[k];
}
}
return 0;
}
NOIP模拟题 2015.8.16 T3
题解：考场上面肉眼感觉这题可以用线段树或者平衡树，但是很关键的问题就是打标记怎么打，我还naive以为这里的T2车跟一般的修改标记没什么很大区别，一般都可以先修改后加减，修改的时候把子树的加减标记也同时改变就不会有问题。但是这里的仔细想想两个操作都是会互相造成影响的，按上面那样打标记是会出现问题的。不过由于输出只有一个数并且数据还是比较良心还算骗到了50分。比暴力还是好点。后来看题解好像要用分块，并且在块上打了四个标记，标程也非常蛋疼，反正并没有看懂= =。而且题解里面还抽逼说什么维护的东西太多线段树是打不了这个的标记的，但是其实线段树平衡树相关还是可以维护这些的。维护的标记不变，但是顺序改为一个节点先下传加减再修改，下传加减的时候把子树的修改加减标记同时修改就可以了，脑补感觉是对的（你是想在我的博客里面找证明这种东西么【斜眼*ei】），而且也过了这道题= =
我是用splay写的，反正每次就暴力找已经废掉的节点删掉，这是n log n的，不过貌似线段树写也差不多的样子，但是好像由于不能删节点好像还要多打点标记的说
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define INF 0x7f7f7f7f
#define m3(x,y,z) min(min(x,y),z)
int c[N][2],fa[N],gf,mi[N],ad[N],xg[N],n,m;
int t[N],sum[N],li[N],ri,ans=0;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Update(int x)
{
mi[x]=m3(t[x],mi[c[x][0]],mi[c[x][1]]);
sum[x]=sum[c[x][0]]+sum[c[x][1]]+1;
}
int Set_up(int x,int y)
{
if (x>y) return 0;
int i=x + y >> 1,j=!i?n+2:i;
mi[j]=t[j];sum[j]=1;
if (x==y) return j;
c[j][0]=Set_up(x,i-1);c[j][1]=Set_up(i+1,y);
fa[c[j][0]]=j;fa[c[j][1]]=j;
Update(j);return j;
}
inline void xgj(int x)
{
if (!x||!xg[x]) return;
t[x]=max(t[x],xg[x]);xg[c[x][0]]=max(xg[c[x][0]],xg[x]);
xg[c[x][1]]=max(xg[c[x][1]],xg[x]);
mi[x]=max(mi[x],xg[x]);xg[x]=0;
}
inline void adj(int x)
{
if (xg[c[x][0]]) xg[c[x][0]]+=ad[x];
if (xg[c[x][1]]) xg[c[x][1]]+=ad[x];
if (!x||!ad[x]) return;
t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];
mi[x]+=ad[x];ad[x]=0;
}
void Rotate(int x)
{
int i=fa[x],j=fa[i],k=c[i][0]==x;
if (j) c[j][c[j][1]==i]=x;else gf=x;
if (c[x][k]) fa[c[x][k]]=i;
c[i][!k]=c[x][k];fa[i]=x;
c[x][k]=i;fa[x]=j;
Update(i);
return;
}
inline void Down(int x)
{adj(x);xgj(x);}
void Up(int x)
{if (fa[x]) Up(fa[x]);Down(x);Down(c[x][0]);Down(c[x][1]);}
void Splay(int x)
{
Up(x);
while (fa[x])
{
if (fa[fa[x]])
Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]);
Rotate(x);
}
Update(x);
return;
}
int Fdown(int x,int y)
{
if (!x) return 0;int k;
if (x==n+2||x<y) {k=Fdown(c[x][1],y);return k?k:x;}
else return Fdown(c[x][0],y);
}
int Fup(int x,int y)
{
if (!x) return 0;int k;
if (x!=n+2&&x>y) {k=Fup(c[x][0],y);return k?k:x;}
else return Fup(c[x][1],y);
}
void Form(int x,int y)
{
int k=Fdown(gf,x),l=Fup(gf,y);
Splay(l);fa[c[l][0]]=0;
Splay(k);Update(gf=fa[c[l][0]=k]=l);
}
void FIT(int x)
{
Down(x);
if (mi[x]>0) return;
if (t[x]<=0) li[++ri]=x;
FIT(c[x][0]);FIT(c[x][1]);
}
inline int Delete(int x)
{
while (c[x][0]||c[x][1]) Rotate(c[x][0]?c[x][0]:c[x][1]);
c[fa[x]][c[fa[x]][1]==x]=0;return fa[x];
}
void up(int x)
{
Down(c[x][0]);Down(c[x][1]);Update(x);
if (fa[x]) up(fa[x]);
}
int main()
{
freopen("road.in","r",stdin);freopen("road.out","w",stdout);
n=Read();m=Read();
for (int k=Read(),i=1;i<=n;i++) t[i]=k;mi[0]=INF;
gf=Set_up(0,n+1);fa[0]=c[0][0]=c[0][1]=0;
while (m--)
{
int k=Read(),q=Read(),w=Read(),e=Read();
if (k==1)
{
Form(q,w);
if (sum[c[c[gf][0]][1]]!=w-q+1) continue;
ad[c[c[gf][0]][1]]=-e;adj(c[c[gf][0]][1]);
if (mi[c[c[gf][0]][1]]<=0) FIT(c[c[gf][0]][1]);
Update(c[gf][0]);Update(gf);ans++;
while (ri--) up(Delete(li[ri+1]));ri++;
} else
if (k==2)
{
Form(q,w);
ad[c[c[gf][0]][1]]=e;adj(c[c[gf][0]][1]);
Update(c[gf][0]);Update(gf);
} else
{
Form(q,w);
xg[c[c[gf][0]][1]]=e;xgj(c[c[gf][0]][1]);
Update(c[gf][0]);Update(gf);
}
}
cout <<ans<<endl;
return 0;
}
