千题目标CategorySubscribe

传送门

题意是给一个长度为n的排列。给出m个询问，每次询问一个区间。

问区间内所有数一个数是另一个数的倍数的对数。

l \le i < j \le r 而且 \min(p_i,p_j) = \gcd(p_i,p_j )

由于是排列，n<=1e5，所以用pos[i]存下i这个数的为位置。

在nlogn的时间里可以找出所有pair的对数，并以(l,r)的二元组表示。

再把询问L,R以二元组的形式离线。

问题转化成了二维偏序问题：L \le l \ \text{and}\ r \le R

用树状数组即可解决

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
typedef pair<int,int> pii;
int pos[maxn], a[maxn];
vector<pii> v;
vector<pair<pii,int> > q;
int c[maxn];
int n, m;
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] ++ ;
}
int ask(int x)
{
    int res = 0;
    

传送门

题意是说，给定一个日期，每个人可以轮流操作，要么将日期+1变为下一天，要么将日期变为下个月的同一天。

当下个月没有同一天的时候，只能讲日期变为下一天。

谁把日期变为2001.11.4即胜利。

是用sg函数做的。

当局面的sg=1的时候必胜。

//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int gap[2020];
int ms[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int sg[2010][13][33];
bool check(int y, int m, int d)
{
    if(y > 2001) return 0;
    else if(y == 2001 && m > 11)  return 0;
    else if(y == 2001 && m==11 && d > 4) return 0;
    return 1;
}
int getsg(int y, int m, int d)
{
    //cerr << y << ":" << m << ":" << d << 

传送门

题意：f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i gcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1]\%(10^9+7)
给定n,a,b求f

打表可知f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i (i-j)[gcd(i,j)=1]\%(10^9+7)

即：\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ i\ [gcd(i,j)=1]-\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ j\ [gcd(i,j)=1]

在i j互质的时候才有值。前面一部分就是每个数与其互质的个数的和，\sum\limits_{i=1}^{n}i\varphi(i)

后面一部分是每个数，与其互质的数值的和。\sum\limits_{i=1}^{n}\frac{i\varphi(i)}{2}(n1)

原因是gcd(n,x)=gcd(n,n-x)，当出现一个与n互质的数x的时候必然有一个n-x成对出现与其互质。他们的和为\frac{n}{2}，但这只是在n1的时候成立。

由于n==1的时候只有一个数字1，所以式子完整来写应该是\sum\limits_{i=1}^{n}\frac{i\varphi(i)+1}{2}因为在i=1的时候答案是1，如果除2就成了1/2，所以在分子上加个1使其成立

完整式子是\sum\limits_{i=1}^{n}\frac{i\varphi(i)-1}{2}

由于n有1e9，线筛是存不下的。
考虑
f=i\varphi(i)=id\varphi(i)
g=id
f*g(n)=\sum\limits_{i|n}\varphi(i)i\frac{n}{i}=n\sum\limits_{i|n}\varphi(i)

然后套杜教筛的板子。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 233;
typedef long long ll;
const ll mod = 1e9 + 7;
ll inv2, inv6;
bool st[maxn];
int primes[maxn], cnt;
ll phi[maxn];
unordered_map<int, ll> up;
ll ksm(ll n, ll k)
{
    

传送门

题意是说给定一个排列，长度1e5，要求支持两种操作：
1. 把某个位置的数字+1e7
2. 给定r, k.查询与前r个数字不同的，并且大于等于k的，最小的数字。

经过分析，答案最大不可能超过n+1。这样的话，操作1其实相当于把这个数字从排列中删去。

用两棵权值线段树，每个点上存的是位置。

对每次2操作，在[k,n]区间里找最靠左的并且val[x]大于r的数。

对每次1操作，最开始是初始化一颗每个点值都是n+1的权值线段树，删掉一个数代表这个数字在区间内可以被使用了。所以在线段树上把点改为该位置。

同时2操作也要找[k,n]区间里最靠左而且val2[x]小于等于r的数。

两个数取最小就是答案。

同时还需记录区间最大最小值，以用来在查询的时候剪枝。

没有这个剪枝，查询会退化为n^2log(n)的，因为区间里可能每个数都会递归到底。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define min(a,b) (a)<(b)?(a):(b)
const int maxn = 1e5 + 233;

struct Node{
    int l, r, v;
}t1[maxn * 4], t2[maxn * 4];
int a[maxn], pos[maxn];
int n;
void build(int p, int l, int r)
{
    if(l == r)
    {
        t1[p].l = l, t1[p].r = 

传送门

题意是说有面值10 20 50 100的钱，有n个价格给定的菜，要求用最少的硬币数量，使得所有n个菜品的价格都能被凑出来。

贪心：直观想法是先用大的面值，依次用小的面值。

这样的话可以发现10， 20， 20， 50四个面值能凑出所有100以内的价格。

但是有个例外：90 110 这样的数据，如果按照上面的贪法是100 50 20 20 10五个硬币，实际上只需要50 20 20 20四个硬币就可以拼出来。

所以进一步发现用10 20 20 20 50五个硬币可以包含所有最优方案。两个10肯定能用一个20代替，四个20肯定能用一个50 20 10代替。

所以做一个10 20 20 20 50的子集生成。然后暴力判断dish[i] % 100 + 100和dish[i] % 100在某个组合的子集生成里有没有。（有先后顺序，第一个如果有了第二个就不用判断。因为既然零钱数量是固定的，那么100圆的越少约好）如果有，100圆的数量就分别是(dish[i] - （dish[i] % 100 + 100）/ 100) ，和dish[i] / 100。

对于100圆判断是个重要细节。
比如1000 90 110这样的数据，1000其中的100圆可以用零钱拼出来，所以100圆个数只有9个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20, 

传送门

题意是说给n<=3e5条宽度为1的线段，长度不定。

要求一个对称轴，使得将图按照对称轴处理以后剩下的线段最多。

首先猜到的就是对称轴必定出现在某个线段的正中央。但是枚举对称轴以后需要用数据结构维护两边的长度。

有一种离线的做法，更为简单。

1. 预处理出每条线的 下边线(l)、中线(l+r1)、上边线(r)。

2. 对于这些预处理出的线，仅仅记录一个y坐标，按照坐标从小到大排序。

3. 枚举这些线当作对称轴，从下往上做扫描线。线性讨论当前这条线和上一条线之间的线段产生的贡献。也就是当前线为对称轴，上一条线为下半段。按照扫描线一层一层的计算面积贡献。

4. 在某个线段遇到中线之前，他的面积贡献都是存在的。因为他按照当前扫描线往上翻折，扫描线下方的面积肯定小 于上方，所以贡献是下方面积的两倍 ，于是下边界的贡献flag = 1。

5. 当扫描线遇到中线的时候，肯定是之前某个线段的中线，此时这条线段在扫描线下方的面积大于等于上方面积，同时这条线段已经达到最大的面积贡献，当扫描线再往上走的时候会减少贡献，每当中线网上移动距离 k 的时候，这条线段就应该减去 2k 的面积贡献。当遇到上边界的时候负贡献消失，变成 0 贡献。于是中线的贡献flag = -2，上边界的flag = 1。

6. 所以用变量cnt对当前层做出贡献的线段条数，面积和sum每次都+=cnt*(i-last)。然后cnt+=当前层数的贡献。因为兑成轴的只可能产生0.5这种小数，于是为了代码方便，把坐标都扩大两倍，同时计算面积的时候不用乘2。

其实最核心的点就是每当对称轴向上移动k距离的时候，整条线就应该缩短2k的距离，这样才能保证图形是对称的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 3e5 + 233;
int n;
vector<pii> a;
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        ll l, r;
        cin >> l >> r;
        a.push_back({l * 

传送门

题意很简单，就是求矩阵的最大子矩阵。

数据范围是坐标很多，但是点最多有2000个。100组数据。

根据x坐标排序。对y坐标进行离散化。

枚举x坐标作为左边界，再依次加入某些x相同的点，这样就确定了右边界。

用线段树维护y方向的区间连续最大和。

总体来说就是枚举左右边界，用区间连续最大和来“确定”上下边界。

联动ACWING126

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2002;
typedef long long ll;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define max(a, b) (a) > (b) ? (a) : (b)
struct Node{
    ll l, r, lsum, rsum, sum, dat;
}t[maxn * 4];
void build(ll p, ll l, ll r)
{
    t[p].l = l; t[p].r = r;
    if(l == r) {t[p].lsum = 0, t[p].rsum = 0, t[p].sum 

传送门

题意是给出若干个一次函数的绝对值，问方程的所有解

把函数按照零点排序，在零点左边的函数都取负，右边都取正。

然后把若干个一次函数看成一个一次函数，用公式直接求解

有个坑点是ax+b=c判断无穷解的时候，除了a等于0以外。还需要b=c，否则是无解，不是无穷解。

#include<bits/stdc++.h>
using namespace std;
typedef __int128 lll;
typedef long long ll;
const int maxn = 1e6 + 233;
typedef pair<ll,ll> pii;
pii v[maxn];
bool cmp(const pii &x, const pii &y)
{
    if( y.first * x.first > 0) return  -x.second * y.first <  -y.second * x.first;
    else return  -x.second * y.first >  -y.second * x.first;
}
bool cmp2(const pii &x, const pii &y)
{
    if( x.second * y.second > 0) return  x.first * y.second <  y.first