P2839[国家集训队]middle二分+可持久化线段树中位数经典做法，二分答案，将小于的部分看做\(-1\)，大于等于的部分看做\(+1\)，那么答案可以更大的条件就是区间和大于等于\(0\)（等于\(0\)可不可以取到看是下取整还是上取整，本题是上取整）。那么问题就是怎么判断有没有这样一个区间

[国家集训队]Crash的数字表格/JZPTAB题目描述今天的数学课上，Crash小朋友学习了最小公倍数（LeastCommonMultiple）。对于两个正整数\(a\)和\(b\)，\(\text{lcm}(a,b)\)表示能同时被\(a\)和\(b\)整除的最小正整数。例如，\(\text{lcm}(6,8)=24\)。回到家后，Crash还在想

原题链接题解先求出以所有最长回文子串，然后记录以每个点作为回文串的右端点时的最小左端点和作为回文串的左端点时的最大右端点code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intr[200005],l[200005],p[200005];voidsolve(){strings;

原题链接题解二分图，分为两类，一类是指向，一类是被指向在这里，只需要建立情人之间的边就行，因为找情人能否成功code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;vector<int>G[10000];intmatch[10000]={0};boolvis[10000]={0};booldfs(intnow)//

借助这道题目把wqs二分讲明白考虑如下一个问题：现在一共有若干个物品，物品被分成两组，现在从中选出若干个物品，但是题目会给出某种限制（也就是在这种限制条件下，物品的选择不是随意的，所有选择集合中，只有一些集合符合题目给出的限制，这样的集合才可以被选择），这种限制只跟物品本身有关而跟

发现可以做如下建图：对于前两组输入，从\(s\)向所有代表学生的点连一条边，容量为其学习文科的喜悦值；从所有代表学生的点向\(t\)连一条边，容量为其学习理科的最大值。对于后四组输入，建两个点\(x,y\)，从\(s\)向\(x\)，从\(y\)向\(t\)分别连容量为相邻两人同时学文/理时额

题目所求即\[\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}\]这里没有出现\([gcd(x,y)=1]\)，所以我们枚举\(gcd\)的值来硬凑，原式就等于\[\sum_{d=1}^{min(n,m)}\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}[gcd(i,j)=d]\]为了出现\([gcd(i,j)=1]\)，直接将\(i,j\)变成\(d\)的倍

发现实际上就是二维静态区间最大值，可以用整体二分维护。时间复杂度\(O((q+n^2)\log\max(a_{i,j})\logn^2)\)。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintW=310005;constintQ=6e4+5;intn,q,w,ans[Q];intc[505][505],m;voidadd(i

Sol:首先注意到答案是具有单调性的，考虑二分答案\(x\)解决。令$up(l,r,x)/down(l,r,x)$是\([l,r]\)中大于等于/小于\(x\)的数。那么对于一个区间\([l,r]\)，显然中位数\(\gex\)的条件为\(up(l,r,x)\gedown(l,r,x)\).变形得到\(up(l,r,x)-down(l,r,

视频链接：   LuoguP1903[国家集训队]数颜色/维护队列//带修莫队O(n^(5/3))#include<iostream>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;constintN=1000005;intn,m,B,mq,mr,a[N];intsum,cnt[N],ans[N];st

视频链接：  LuoguP1494[国家集训队]小Z的袜子//普通莫队O(n*sqrt(n))#include<iostream>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;constintN=50005;intn,m,B,a[N];intsum,cnt[N],ans1[N],ans2[N];str

题目链接：排队水紫，\(n\)不大，树套树或者分块都能做。分块的话，最优序列分块套套值域分块最优。观察到是可差性问题维护，即权值数量维护，那我们就树状数组套权值线段树即可。由于\(n\)不大，我们可以不用回收标记，直接数组空间开大点就行。我们预处理出初始逆序对，每一次操作都是基于

题目链接：https://www.luogu.com.cn/problem/P4555题解：要找一个由两个回文组成字符串，一定有一个分割的位置，将两个回文串分开，设分割x,x+1,可能成为最后答案的值一定是左边的最长回文串和右边的最长的回文串长度之和。   回文中心一个<x,一个>x+1且一定包含x和x+1。如果最

题目的等差子序列最少只要求长度为3，那么其实就转化为对于一个数是否存在左右各一个与它差值相等的一对数，比如14325中1，5对3来说就如此。这样的关系放到数轴上就是是否存在一对数到某数的距离相等。由于题目明确是一个排列，也就是1到n所有数一定会出现一次，那么对于某数，它左边的

添加分隔符的目的是给偶数长度的回文串一个中心，本题只要求奇数长度的回文串，那么这一步就可以省略了；而且，字符串加法非常慢利用回文串的另一半所携带的信息，注意不能超出回文串的范围边修改边询问，才需要用到高级数据结构；如果所有修改都在询问之前，就不需要了点击查看代码#inclu

[国家集训队]矩阵乘法题目描述给你一个\(n\timesn\)的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第\(k\)小数。输入格式第一行有两个整数，分别表示矩阵大小\(n\)和询问组数\(q\)。第\(2\)到第\((n+1)\)行，每行\(n\)个整数，表示这个矩阵。第\((i+1)\)行

题意给定一个矩阵，每次询问子矩阵的第\(k\)大。Sol考虑把莫队扔到二维上来做。发现复杂度变为：\(O(n^2q^{\frac{3}{4}})\)。卡卡常就过了。Code#include<iostream>#include<algorithm>#include<cstdio>#include<array>#include<cmath>#include<vector>#i

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e6+10;intn,m;intk[N],a,b,c;intval[N];//如果一条边的两端点被同一个人选了，那么产生边权的贡献//把边权均分到两端点上，每个端点加上c/2//如果这条边被同一个选了，那

P2757[国家集训队]等差子序列在线段树存哈希的时候，注意字符长度的改变，否则query会崩掉lolquery(intu,intl,intr,intlft,intrht){if(lft<=l&&r<=rht)returntr[u];else{intmid=(l+r)>>1;if(rht<=

题目大意对于等式\(\displaystyle\sum_{i=1}^{n}a_ix_i=b\)求有多少\(b\in[l,r]\)使得等式存在非负数解。思路典型的同余最短路，可先看看跳楼机（题解）。首先想到将区间\([l,r]\)分开，分为\([0,l-1]\)和\([0,r]\)再答案相减。所以我们只需要能求得\([0,x]\)的答案即

题目链接首先我们考虑用图论的边描述这个关系。若两者存在夫妻或情侣关系，就连一条边（是有向边还是无向边呢？）。先来考虑两对夫妻的情况，若夫妻边与情侣边交替出现。且一对夫妻在同一个环内，则可以说明分开后能够重新找到另一半。如下图：夫妻a-男b-女c-男d-女情侣a-男d-女c-

Problem一个长度为\(n\)的序列\(a\)，设其排过序之后为\(b\)，其中位数定义为\(b_{n/2}\)，其中\(a,b\)从\(0\)开始标号，除法下取整。给你一个长度为\(n\)的序列\(s\)。回答\(Q\)个这样的询问：\(s\)的左端点在\([a,b]\)之间，右端点在\([c,d]\)之间的子区间中，最大的中

WC2019数树P4463国家集训队calc

2021陈雨昕《太阳神的宴会》命题报告代晨昕后缀树的构建邓明扬一类调整算法在信息学竞赛中的应用可能有交丁晓漫再探线性规划对偶在信息学竞赛中的应用...郭城志浅谈信息学竞赛中的弦图问题

一、题目描述：给你一个长度为$n$的序列$a$,你需要进行$m$次操作。$类型\1\:将第\x\个元素的值修改为\v\。$$类型\2\:求区间\l\到\r\中有多少种数字。$数据范围：$1\len,m\le1333333,所有数字\le1\times10^6$ 二、解题思路：带