对参加ACM竞赛非常有用的几个ACM答题模板（数论

				//线段树
				//可以处理加入边和删除边不同的情况
				//inc_seg和dec_seg用于加入边
				//seg_len求长度
				//t传根节点(一律为1)
				//l0,r0传树的节点范围(一律为1..t)
				//l,r传线段(端点)
				#define MAXN 10000
				struct segtree{
					int n,cnt[MAXN],len[MAXN];
					segtree(int t):n(t){
						for (int i=1;i							cnt[i]=len[i]=0;
					};
					void update(int t,int l,int r);
					void inc_seg(int t,int l0,int r0,int l,int r);
					void dec_seg(int t,int l0,int r0,int l,int r);
					int seg_len(int t,int l0,int r0,int l,int r);
				};
				
				int length(int l,int r){
					return r-l;
				}
				
				void segtree::update(int t,int l,int r){
					if (cnt[t]||r-l==1)
						len[t]=length(l,r);
					else
						len[t]=len[t+t]+len[t+t+1];
				}
				
				void segtree::inc_seg(int t,int l0,int r0,int l,int r){
					if (l0==l&&r0==r)
						cnt[t]++;
					else{
						int m0=(l0+r0)>>1;
						if (l							inc_seg(t+t,l0,m0,l,m0						if (r>m0)
							inc_seg(t+t+1,m0,r0,m0>l?m0:l,r);
						if (cnt[t+t]&&cnt[t+t+1]){
							cnt[t+t]--;
							update(t+t,l0,m0);
							cnt[t+t+1]--;
							update(t+t+1,m0,r0);
							cnt[t]++;
						}
					}
					update(t,l0,r0);
				}
				
				void segtree::dec_seg(int t,int l0,int r0,int l,int r){
					if (l0==l&&r0==r)
						cnt[t]--;
					else if (cnt[t]){
						cnt[t]--;
						if (l>l0)
							inc_seg(t,l0,r0,l0,l);
						if (r							inc_seg(t,l0,r0,r,r0);
					}
					else{
						int m0=(l0+r0)>>1;
						if (l							dec_seg(t+t,l0,m0,l,m0						if (r>m0)
							dec_seg(t+t+1,m0,r0,m0>l?m0:l,r);
					}
					update(t,l0,r0);
				}
				
				int segtree::seg_len(int t,int l0,int r0,int l,int r){
					if (cnt[t]||(l0==l&&r0==r))
						return len[t];
					else{
						int m0=(l0+r0)>>1,ret=0;
						if (l							ret+=seg_len(t+t,l0,m0,l,m0						if (r>m0)
							ret+=seg_len(t+t+1,m0,r0,m0>l?m0:l,r);
						return ret;
					}
				}