SPOJ 3267 DQUERY（离线+树状数组）
传送门话说这好像HH的项链啊……然后就说一说上次看到的一位大佬很厉害的办法吧对于所有$r$相等的询问，需要统计有多少个不同的数，那么对于同一个数字，我们只需要关心它最右边的那一个比如$1,2,3,4,1,2$，对于所有$r=5$的询问，我们不用去管第一个$1$因为它一定可以被第五个$1$代替同理，对...
spoj 104 Highways (最小生成树计数)
题目链接：http://www.spoj.pl/problems/HIGH/题意：求最小生成树个数。#include<algorithm>#include<cstdio>#include<cmath>#include<cstring>#include&...
树链剖分边权模板spoj375
树链剖分是树分解成多条链来解决树上两点之间的路径上的问题如何求出树链：第一次dfs求出树上每个结点的大小和深度和最大的儿子，第二次dfs就能将最大的儿子串起来并hash（映射）到线段树上（或者其他数据结构上），这就是一条重链。一些性质：1.在树链上进行的算法要额外乘以一个logn：因为找u，v的lc...
[SPOJ - QTREE] Query on a tree（树链剖分 - 边权最大值）
题目传送门：[SPOJ-QTREE] Queryonatree 题目大意：存在一个树，树上有n个节点和n-1条边，对这棵树进行以下两种操作CHANGE i ti ：将树的第i条边的权值改为tiQUERYa b：查询a->b路径中权值最大的边的值分析：边权树链剖分裸题，CHANGE操作是更改第i...
SPOJ 227 Ordering the Soldiers 线段树 / 树状数组
题意：设原数组为a[i]，pos[i]代表第i个位置之前有多少个数比a[i]大，求原数组a[i]。这个题意是看了别人的题解才明白，我自己没读出来……方法：假设我们从左往右放，因为后面的数还有可能影响前面的数的位置，所以在最后一个数放完之前，我们没法确定每个数的位置，所以我们反过来考虑，从右往左放。因...
有人能告诉我为什么我的代码会在SPOJ上产生一个分割吗?什么是分割错误?(fctrl - 2)
#include<stdio.h>#include<iostream>#include<string>#include<string.h>usingnamespacestd;chararr[200],res[200];chartable[150][20...
spoj mpoint
题解：判断每一次加进来的时候有几个被破坏，几个添加然后单调栈维护代码：#include<bits/stdc++.h>usingnamespacestd;constintN=;intn,j,k,ans=,now,oo=;structnote{intx,y,id;}a[N],b[N];boo...
SPOJ 104 HIGH - Highways 生成树计数
题目链接：https://vjudge.net/problem/SPOJ-HIGH解法：生成树计数1、构造基尔霍夫矩阵（又叫拉普拉斯矩阵）n阶矩阵若u、v之间有边相连C[u][v]=C[v][u]=-1矩阵对角线为点的度数2、求n-1阶主子式的行列式的绝对值去掉第一行第一列初等变换消成上三角矩阵对角...
[BZOJ 2480] [SPOJ 3105] Mod
Description已知数\(a,p,b\)，求满足\(a^x\equivb\pmodp\)的最小自然数\(x\)。Input每个测试文件中最多包含\(100\)组测试数据。每组数据中，每行包含\(3\)个正整数\(a,p,b\)。当\(a=p=b=0\)时，表示测试数据读入完全。Output对于...
Spoj1771-Yet Another N-Queen Problem(精确覆盖)
DescriptionAftersolving Solutiontothe n QueensPuzzle byconstructing,LoadingTimewantstosolveaharderversionoftheN-QueenProblem.Somequeenshavebeensetonpa...
Can you answer these queries I SPOJ - GSS1 （线段树维护区间连续最大值/最大连续子段和）
YouaregivenasequenceA[1],A[2],...,A[N].(|A[i]|≤15007,1≤N≤50000).Aqueryisdefinedasfollows:Query(x,y)=Max{a[i]+a[i+1]+...+a[j];x≤i≤j≤y}.GivenMqueries,yo...
HDU 4348.To the moon SPOJ - TTM To the moon -可持久化线段树(带修改在线区间更新(增减)、区间求和、查询历史版本、回退到历史版本、延时标记不下放(空间优化))
TothemoonTimeLimit:4000/2000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):8372 AcceptedSubmission(s):1986ProblemDescri...
SPOJ COT3 Combat on a tree（Trie树、线段树的合并）
题目链接：http://www.spoj.com/problems/COT3/AliceandBobareplayingagameonatreeofnnodes.Eachnodeiseitherblackorwhiteinitially.Theytaketurnstodothefollowingop...
SPOJ 3273 - Order statistic set ， Treap
点击打开链接题意：集合S支持一下四种操作： INSERT(S,x): 假设S中没有x，则插入xDELETE(S,x): 假设S中有x，则删除xK-TH(S): 输出S中第K小的数COUNT(S,x): 统计S中小于x的数有多少个一共同拥有Q（1≤Q≤200000）次操作。Treap模板。...
随便玩玩系列之一：SPOJ-RNG+51nod 算法马拉松17F+51nod 1034 骨牌覆盖v3
先说说前面的SPOJ-RNG吧，题意就是给n个数，x1,x2,...,xn每次可以生成[-x1,x1]范围的浮点数，把n次这种操作生成的数之和加起来，为s，求s在[A,B]内的概率连续形的概率假设有3步，那整个分布范围相当于一个立体几何图形，上界b和下界a可当成一个x+y+z=a或b的平面看待，算出...
SPOJ DQUERY树状数组离线or主席树
D-queryTimeLimit: 227MS MemoryLimit: 1572864KB 64bitIOFormat: %lld&%lluSubmit StatusDescriptionEnglishVietnameseGivenasequenceofnnumbersa1,a2,...,...
spoj1811 Longest Common Substring
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#definemaxn500005#definemaxl250005u...
【SPOJ】DIVCNTK min_25筛
题目大意给你\(n,k\)，求\[S_k(n)=\sum_{i=1}^n\sigma_0(i^k)\]对\(2^{64}\)取模。题解一个min_25筛模板题。令\(f(n)=\sigma_0(n^k)\)，那么\(S_k(n)=\sum_{i=1}^nf(i)\)，而且\[\begin{cases...
SPOJ GSS1 静态区间求解最大子段和
题目大意：给定n个数，再给q个区间询问，希望在区间s,t中找到一段连续的子序列使其和最大因为询问上万，节点数50000，明显是用线段树去做，这里很明显的区间更新，唯一写起来有点恶心的是询问每一个区间的最大都要跟左右区间的左最大右最大有关系反正时要注意细节了，查询的时候同时要查询其左右连续最大自己的错...
SPOJ—VLATTICE Visible Lattice Points（莫比乌斯反演）
http://www.spoj.com/problems/VLATTICE/en/题意：给一个长度为N的正方形，从（0,0,0）能看到多少个点。思路：这道题其实和能量采集是差不多的，只不过从二维上升到了三维。分三部分计算：①坐标值上的点，只有3个。②与原点相邻的三个表面上的点，需满足gcd（x，y）...