#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int a[maxn],c[maxn]; struct dd { int x,id; dd(int xx=0,int yy=0):x(xx),id(yy) { } bool operator <(const dd&aa)const { return x<aa.x; } }; dd b[maxn]; int lowbit(int x) { return x&(...

https://www.luogu.org/problem/P1196 #include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int fa[maxn],sum[maxn],son[maxn]; struct dd { int faa,val; dd(int xx=0,int yy=0):faa(xx),val(yy) { } }; int getf(int x) { if(fa[x]==x)return x; else { int fa1=get...

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; struct dd { int to,cost; dd(int xx=0,int yy=0):to(xx),cost(yy) { } bool operator >(const dd&aa)const { return cost>aa.cost; } }; priority_queue<dd,vector<dd>,greater<dd> &gt...

那么 显然我们应该把最大的k个数放进去。单次复杂度n*log(n)；可以接受牛客上的题太坑l。。。。。。。。https://loj.ac/problem/149 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; long long a[maxn], b[maxn], new1[maxn]; int n, m; bool check(long long x) { priority_queue<long long> op; for (int i = 1; i &...

求解一组解让ax+by=gcd（a,b）; 同余方程 假如我们要求解a* x三等b%（p）那么等同于 （ax-b）%p==0;不妨设为y倍ax+py=b；*-_-!**就这样好像就可以了。假如b==1那么只需要求出一组解ax+py=1；同余方程 #include<bits/stdc++.h> using namespace std; struct dd { int gcd,x1,y1; dd(int xx=0,int yy=0,int zz=0):gcd(xx),x1(yy),y1(zz) {} }; dd exgcd(int x,int y) { //if...

1 先考虑只有n的时候怎么求。。。。。。。。。。。。 First【x】表示x处的数，在他之前最先出现的是哪里。 Dp[i]表示到i的时候，他的所有子区间的和； 没有出现过。。 Dp1是i前面包括i的子区间的和 Dp[x]=dp[x-1]+dp1[x]; 第一次出现的位置为r Dp[x]=dp[x-1]+dp1[x]; 考虑长度小于等于n的序列。 Point 30 当k==2 用同样的方式求一个dp[2*n]; 找规律 等差数列 一共有k-2项 公差是d D=i-first[i]; 推到3.。。...

dp[k]表示把前k个分成若干组，这时候他后面都已经加上了，应该多加的数。 就是dp[k]=ans_k+x(组数)*sum_ans(k+1,n); dp[k]->dp[i] Ask（l，r）代表l到r的最大值减去最小值 用st搞出来 Ans_sum/sum_ans都代表前缀和 Cost（l,r）代表l到r的ask+sum。 方法一：数学推导 Dp[k]=ans_k+x(组数)*sum_ans(i+1,n)+x*sum_ans(k+1,i); Dp[i]=ans_i+ans_sum(i+1,n)*(x+1) =ans_k+ans_sum...

抗议！！！！卡我大爆搜~~却把错误贪心过了