杭电多校2021补题记录
Pty loves lines
#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 3e7+5;
using namespace std;
int kase,n;
const int m=700;
int f[maxn];
int main()
{
FAST;
memset(f,INF,sizeof(f));
f[0]=0;
for (int i=1; i<=m*(m-1)/2; i++)
{
for (int k=2; k*(k-1)<=2*i; k++)
f[i]=min(f[i],f[i-k*(k-1)/2]+k);
}
cin>>kase;
while(kase--)
{
cin>>n;
for (int i=n*(n-1)/2; i>=1; i--)
if (f[i]<=n) cout<<n*(n-1)/2-i<<' ';
cout<<n*(n-1)/2<<endl;
}
return 0;
}
CCPC Strings
#include <cstdio>
typedef long long Lint;
const Lint mod = 1e9 + 7;
Lint fpow(Lint a, Lint n) {
Lint res = 1;
for (; n; n >>= 1) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}
Lint minv(Lint a) { return fpow(a, mod - 2); }
Lint ainv(Lint a) { return mod - a; }
Lint mod_add(Lint a, Lint b) { return (a + b) % mod; }
Lint mod_mul(Lint a, Lint b) { return a * b % mod; }
Lint kn1n(Lint k, Lint n) { return n % 2 ? ainv(k) : k; }
const Lint inv1 = minv(54);
const Lint inv2 = minv(27);
const Lint inv3 = mod_mul(2, inv2);
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
int r = n % 3, k = n / 3;
Lint res = 0;
if (r == 0) {
res = mod_mul(inv1, mod_add(kn1n(8, k), mod_mul(mod_add(mod_mul(9, k), ainv(8)), fpow(8, k))));
} else if (r == 1) {
res = mod_mul(inv2, mod_add(kn1n(5, k), mod_mul(mod_add(mod_mul(9, k), ainv(5)), fpow(8, k))));
} else {
res = mod_mul(inv3, mod_add(kn1n(2, k), mod_mul(mod_add(mod_mul(9, k), ainv(2)), fpow(8, k))));
}
printf("%lld\n", res);
}
return 0;
}Calculate
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
#define int long long
const int mod=1e9+7;
int qmi(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int cal1(int x1,int x2){
int ans=0;
int h=x2/x1;
h--;
ans=x1*h%mod*(2*h+1)%mod*(h+1)%mod*qmi(6,mod-2)%mod;
//cout<<x1<<" "<<x2<<" "<<ans<<endl;
h=(x2-((x2/x1)*x1))+1;
ans=(ans+h*(x2/x1)%mod*(x2/x1)%mod)%mod;
return ans;
}
int cal2(int x1,int x2){
int ans=0;
for(int x=x1,gx;x<=x2;x=gx+1){
gx=x2/x?min(x2/(x2/x),x2):x2;
int u1=x/x1,u2=gx/x1;
int f=0;
if(u1==u2)f=(f+(gx-x+1)*u1%mod)%mod;
else if((u1+1)==u2){
int z=x1*u2%mod;
z--;
f=(f+((z-x+1)%mod+mod)%mod*u1%mod)%mod;
f=(f+((gx-z)%mod+mod)%mod*u2%mod)%mod;
}else{
f=(f+(u1+1+u2-1)*(u2-1-u1-1+1)%mod*qmi(2,mod-2)%mod*x1%mod)%mod;
int z=(u1+1)*x1%mod;
z--;
f=(f+(z-x+1)*u1%mod)%mod;
z=x1*u2%mod;
f=(f+(gx-z+1)*u2%mod)%mod;
}
ans=(ans+2*f*(x2/x)%mod)%mod;
}
return ans;
}
int cal3(int x1,int x2){
int ans=0;
for(int x=x1,gx;x<=x2;x=gx+1){
gx=(x2/x)?min(x2/(x2/x),x2):x2;
ans=(ans+(x2/x)*(x2/x)*(gx-x+1)%mod)%mod;
// cout<<x<<"zz"<<gx<<endl;
}
return ans;
}
int cal4(int x1,int x2,int y1,int y2){
int ans=0;
int h=x2/x1;
h--;
ans=x1*h%mod*(h+1)%mod*qmi(2,mod-2)%mod;
h=(x2-((x2/x1)*x1))+1;
ans=(ans+h*(x2/x1)%mod)%mod;
//cout<<"hh"<<ans<<endl;
int ans1=0;
h=y2/y1;
h--;
ans1=y1*h%mod*(h+1)%mod*qmi(2,mod-2)%mod;
h=(y2-((y2/y1)*y1))+1;
ans1=(ans1+h*(y2/y1)%mod)%mod;
return 2*(ans*ans1)%mod;
}
int cal5(int x1,int x2,int y1,int y2){
int ans1=0;
int h=y2/y1;
h--;
ans1=y1*h%mod*(h+1)%mod*qmi(2,mod-2)%mod;
h=(y2-((y2/y1)*y1))+1;
ans1=(ans1+h*(y2/y1)%mod)%mod;
int ans=0;
for(int x=x1,gx;x<=x2;x=gx+1){
gx=x2/x?min(x2/(x2/x),x2):x2;
ans=(ans+(x2/x)*(gx-x+1))%mod;
}
return ans1*ans%mod*2%mod;
}
int cal6(int x1,int x2,int y1,int y2){
int ans=0;
for(int x=x1,gx;x<=x2;x=gx+1){
gx=x2/x?min(x2/(x2/x),x2):x2;
ans=(ans+(x2/x)*(gx-x+1))%mod;
}
int ans1=0;
for(int x=y1,gx;x<=y2;x=gx+1){
gx=y2/x?min(y2/(y2/x),y2):y2;
ans1=(ans1+(y2/x)*(gx-x+1))%mod;
}
return 2*ans1%mod*ans%mod;
}
signed main(){
int T;
cin>>T;
while(T--){
int x1,x2,y1,y2;
scanf("%lld%lld%lld%lld",&x1,&x2,&y1,&y2);
int ans=0;
int h=0;
ans=(ans+(y2-y1+1)*cal1(x1,x2)%mod)%mod;
//cout<<ans<<endl;
ans=(ans+(y2-y1+1)*cal2(x1,x2)%mod)%mod;
ans=(ans+(y2-y1+1)*cal3(x1,x2)%mod)%mod;
// cout<<ans<<endl;
ans=(ans+(x2-x1+1)*cal1(y1,y2)%mod)%mod;
// cout<<cal1(y1,y2)<<endl;
ans=(ans+(x2-x1+1)*cal2(y1,y2)%mod)%mod;
// cout<<cal2(y1,y2)<<endl;
ans=(ans+(x2-x1+1)*cal3(y1,y2)%mod)%mod;
// cout<<cal3(y1,y2)<<endl;
// cout<<ans<<endl;
ans=(ans+cal4(x1,x2,y1,y2))%mod;
// cout<<cal4(x1,x2,y1,y2)<<endl;
ans=(ans+cal5(x1,x2,y1,y2))%mod;
ans=(ans+cal5(y1,y2,x1,x2))%mod;
ans=(ans+cal6(x1,x2,y1,y2))%mod;
cout<<ans<<endl;
}
return 0;
}
Sequence
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=15;
struct SegTree{
int l,r,mx,lz,val;
}Tr[N<<2];
int f[N][M];
bool vis[N];
int ls[N];
int lss[N];
int a[N];
int cnt[N];
void pushup(int u)
{
Tr[u].mx=max(Tr[u<<1].mx,Tr[u<<1|1].mx);
}
void pushdown(int u)
{
if(Tr[u].lz)
{
int k=Tr[u].lz;
Tr[u<<1].mx+=k;
Tr[u<<1|1].mx+=k;
Tr[u<<1].lz+=k;
Tr[u<<1|1].lz+=k;
Tr[u].lz=0;
}
}
void build(int u,int l,int r,int op)
{
Tr[u].l=l,Tr[u].r=r;Tr[u].lz=0;
if(l==r)
{
Tr[u].mx=f[l][op];
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid,op);
build(u<<1|1,mid+1,r,op);
pushup(u);
}
void add(int u,int l,int r,int k)
{
if(r<l) return;
if(l>Tr[u].r||r<Tr[u].l) return;
if(l<=Tr[u].l&&r>=Tr[u].r)
{
Tr[u].mx+=k;
Tr[u].lz+=k;
return;
}
pushdown(u);
add(u<<1,l,r,k);
add(u<<1|1,l,r,k);
pushup(u);
}
int query(int u,int l,int r)
{
if(l>Tr[u].r||r<Tr[u].l) return 0;
pushdown(u);
if(l<=Tr[u].l&&Tr[u].r<=r) return Tr[u].mx;
return max(query(u<<1,l,r),query(u<<1|1,l,r));
}
int n,m;
void run()
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
vis[a[i]]=0,cnt[a[i]]=0;
for(int i=1;i<=n;i++)
{
if(!vis[a[i]]) f[i][1]=f[i-1][1]+1;
else
{
cnt[a[i]]++;
if(cnt[a[i]]==1) f[i][1]=f[i-1][1]-1;
}
vis[a[i]]=true;
}
for(int i=2;i<=m;i++)
{
build(1,1,n,i-1);
for(int j=1;j<=n;j++) ls[a[j]]=0;
for(int j=1;j<=n;j++)
{
add(1,max(1,ls[a[j]]),j-1,1);
add(1,lss[a[j]],ls[a[j]]-1,-1);
lss[a[j]]=ls[a[j]];
ls[a[j]]=j;
f[j][i]=query(1,1,j);
}
}
printf("%d\n",f[n][m]);
}
int main()
{
while(scanf("%d%d",&n,&m)){
run();
}
return 0;
}Dota2 Pro Circuit
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5010;
struct node{
long long x;
int i;
}a[maxn];
bool cmp(node x,node y){
return x.x<y.x;
}
long long b[maxn];
int ans1[maxn],ans2[maxn];
int c[maxn];
bool vis[maxn];
signed main(){
// freopen("input.txt","r",stdin);
// freopen("123.out","w",stdout);
// freopen();
int T;
cin>>T;
while(T--){
int n;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i].x);
a[i].i=i;
}
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
sort(b+1,b+1+n);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)c[j]=a[j].x;
c[i]=a[i].x;
c[i]+=b[n];
int l=1,r=n-1;
int pos=0;
while(l<=r){
int mid=(l+r)>>1;
if((c[i+1]+b[mid])<=c[i]){
l=mid+1;
pos=mid;
}else{
r=mid-1;
}
}
int cnt=0;
for(int j=pos,k=1;j>=1&&((k+i)<=n);j--,k++){
if(c[i]>=(c[i+k]+b[j])){
cnt++;
}else{
k--;
}
}
ans1[a[i].i]=n-(i+cnt)+1;
cnt=0;
c[i]=a[i].x;
c[i]+=b[1];
int h=c[i];
pos=0;
for(int j=i+1;j<=n;j++){
if(c[j]>c[i]){
pos=j;
break;
}
}
// cout<<"gGG"<<pos<<endl;
if(pos){
cnt+=(n-pos+1);
}
if(pos==0)pos=n+1;
int u=0;
for(int j=1;j<pos;j++){
if(j==i)continue;
c[++u]=a[j].x;
}
//cout<<"GG"<<u<<endl;
pos=0;
l=2;r=n;
//cout<<c[u]<<"ZZ"<<c[i]<<endl;
while(l<=r){
int mid=(l+r)>>1;
if((c[u]+b[mid])>h){
r=mid-1;
pos=mid;
}else{
l=mid+1;
}
}
// cout<<"jj"<<pos<<endl;
if(pos){
for(int j=pos,k=u;j<=n&&(k>=1);j++,k--){
if((c[k]+b[j])>h){
cnt++;
}else{
k++;
}
}
}
ans2[a[i].i]=cnt+1;
}
for(int i=1;i<=n;i++){
printf("%lld %lld\n",ans1[i],ans2[i]);
}
}
return 0;
}Ink on paper
#include<iostream>
#include<cstring>
using namespace std;
long long a[5010][5010];
long long x[5010];
long long y[5010];
long long d[5010];
bool v[5010];
int n;
void prim(){
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[1]=0;
for(int i=1;i<n;i++){
int x=0;
for(int j=1;j<=n;j++)
if(!v[j]&&(x==0||d[j]<d[x]))x=j;
v[x]=1;
for(int y=1;y<=n;y++){
if(!v[y])d[y]=min(d[y],a[x][y]);
}
}
}
int main(){
int T;
cin>>T;
while(T--){
// int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
}
prim();
long long ans=0;
for(int i=2;i<=n;i++){
ans=max(ans,d[i]);
}
printf("%lld\n",ans);
}
return 0Counting Stars
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int maxn = 100050;
long long a[maxn + 10];
long long P[6*maxn];
struct tree
{
int l, r;
long long jan;
long long fla;
long long sum;
long long pre;
}t[8* maxn + 2];
long long lowbit(long long x){
return x&(-x);
}
void push_up(int p){
t[p].pre =(t[p*2].pre + t[p*2+1].pre)%mod;
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
t[p].jan=t[p*2].jan+t[p*2+1].jan;
}
void build(int p, int l, int r)
{
t[p].jan=0;
t[p].fla=0;
t[p].sum=0;
t[p].pre=0;
t[p].l = l, t[p].r = r;
if (l == r)
{
int pos=0;
t[p].jan=0;
t[p].fla=0;
t[p].sum=0;
t[p].pre=0;
t[p].pre=a[l];
long long f=1;
while(a[l]){
if(a[l]&1){
t[p].jan++;
t[p].sum=f;
}
a[l]>>=1;
f=f*2;
}
t[p].pre=t[p].pre-t[p].sum;
//cout<<l<<"SS"<<t[p].jan<<endl;
return;
}
int mid = (l + r) / 2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
push_up(p);
}
void spread(int p)
{
if (t[p].fla)
{
t[p*2].sum=t[p*2].sum*P[t[p].fla]%mod;
t[p * 2 + 1].sum=t[p*2+1].sum*P[t[p].fla]%mod;
t[p * 2].fla += t[p].fla;
t[p * 2 + 1].fla += t[p].fla;
t[p].fla = 0;
}
}
void change(int p, int x, int y)
{
if(t[p].jan==0)return;
if(y<t[p].l||x>t[p].r)return;
if (t[p].l==t[p].r)
{
if(t[p].jan==0){
t[p].jan=0;
t[p].fla=0;
t[p].sum=0;
t[p].pre=0;
return;
}
t[p].jan--;
t[p].pre-=lowbit(t[p].pre);
// t[p].pre-=(t[p].pre&(-t[p].pre));
//cout<<t[p].jan<<"SS"<<endl;
if(t[p].jan==0){
t[p].jan=0;
t[p].fla=0;
t[p].sum=0;
t[p].pre=0;
return;
}
return;
}
spread(p);
int mid = (t[p].l + t[p].r)>>1;
if (x <= mid)
change(p*2,x,y);
if (y > mid)
change(p*2+1,x,y);
push_up(p);
}
void change1(int p, int x, int y)
{
// cout<<"YY"<<endl;
if(t[p].jan==0)return;
if (x <= t[p].l && y >= t[p].r)
{
t[p].fla++;
t[p].sum=t[p].sum*2%mod;
return;
}
spread(p);
int mid = (t[p].l + t[p].r) >>1;
if (x <= mid)
change1(p * 2, x, y);
if (y > mid)
change1(p * 2 + 1, x, y);
push_up(p);
}
long long ask(int p, int x, int y)
{
if(t[p].jan==0)return 0;
//cout<<"rrrr"<<endl;
if (x <= t[p].l && y >= t[p].r)
{
return (t[p].pre+t[p].sum)%mod;
}
spread(p);
int mid = (t[p].l + t[p].r) / 2;
long long ans = 0;
if (x <= mid) ans=(ans+ask(p * 2, x, y))%mod;
if (y > mid) ans=(ans+ask(p * 2 + 1, x, y))%mod;
return ans;
}
signed main()
{
P[0]=1;
for(int i=1;i<=500000;i++){
P[i]=P[i-1]*(long long)(2)%mod;
}
int T;
cin>>T;
while(T--){
int n, m;
scanf("%lld",&n);
for (int i = 1;i <= n;i++)
scanf("%lld",&a[i]);
build(1, 1, n);
scanf("%lld",&m);
for(int i =1;i <=m;i++){
int q, x, y;
scanf("%lld",&q);
if (q == 1){
scanf("%lld%lld",&x,&y);
if(x>y)swap(x,y);
//cout<<"JH";
printf("%lld\n",ask(1, x, y));
}
else if(q==2){
scanf("%lld%lld",&x,&y);
if(x>y)swap(x,y);
change(1, x, y);
}else{
scanf("%lld%lld",&x,&y);
if(x>y)swap(x,y);
change1(1, x, y);
}
}
}
return 0;
}Yiwen with Sqc
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=998244353;
const double eps=1e-6;
char s[maxn];
int sum[30];
ll dp[maxn];
signed main(){
int T; scanf("%d",&T);
while(T--){
cin>>s+1;
int n=strlen(s+1);
for(int i=0;i<=29;i++){
sum[i]=0;
}
long long ans=0;
for(int i=1;i<=n;i++){
int now=s[i]-'a'+1;
dp[i]=(dp[i-1]+2*sum[now]+i)%mod;
ans=(ans+dp[i])%mod;
sum[now]=(sum[now]+i)%mod;
}
cout<<ans<<endl;
}
return 0;
}Link with Limit
#include <stdio.h>
#include <queue>
#define MN 100000
typedef long long ll;
int n,a[MN+5],din[MN+5];
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
din[i] = 0;
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
din[a[i]]++;
}
std::queue<int> Q;
for(int i=1;i<=n;i++){
if(din[i]==0) Q.push(i);
}
while(!Q.empty()){
int u = Q.front();
Q.pop();
din[a[u]]--;
if(din[a[u]]==0){
Q.push(a[u]);
}
}
ll p=-1,q=-1;
for(int i=1;i<=n;i++){
if(din[i]==0) continue;
ll tp=0,tq=0;
for(;din[i];i=a[i]){
tp += i;
tq++;
din[i] = 0;
}
if(p==-1){
p = tp;
q = tq;
}else{
if(p*tq!=q*tp){
puts("NO");
return;
}
}
}
puts("YES");
return;
}
int main(){
int T;
scanf("%d",&T);
while(T--) solve();
}zoto
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e5+10;
int T,n,m,k,a[maxn],len;
struct Node{
int l,r,id;
int u,v;
bool operator<(const Node &x) const {
if (l /len!= x.l /len) return l < x.l;
return (l /len) & 1 ? r < x.r : r > x.r;
}
}node[maxn];
bool cmp(Node x,Node y){
if(x.l/len==y.l/len)
return x.r<y.r;
return x.l<y.l;
}
int ans1[maxn];
int num[maxn],cnt[maxn];
void add(int x){
if(num[x]==0){
num[x]++;
cnt[x/len]++;
}
else{
num[x]++;
}
}
void del(int x){
num[x]--;
if(num[x]==0){
cnt[x/len]--;
}
}
int cal(int x){
int sum=0;
for(int i=0;i<x/len;i++){
sum+=cnt[i];
}
for(int i=(x/len)*len;i<=x;i++){
sum+=(num[i]>0);
}
return sum;
}
int main(){
int t;
cin>>t;
while(t--){
memset(num,0,sizeof(num));
memset(cnt,0,sizeof(cnt));
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);//坐标为(i,a[i]);
}
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&node[i].l,&node[i].u,&node[i].r,&node[i].v);//坐标为x0,y0,x1,y1
node[i].id=i;
}
len=sqrt(n);
sort(node+1,node+1+m);
for(int i=1,l=1,r=0;i<=m;i++){
while(l>node[i].l){
add(a[--l]);
}
while(r<node[i].r){
add(a[++r]);
}
while(l<node[i].l){
del(a[l++]);
}
while(r>node[i].r){
del(a[r--]);
}
ans1[node[i].id]=cal(node[i].v)-cal(node[i].u-1);
}
for(int i=1;i<=m;i++){
printf("%lld\n",ans1[i]);
}
}
}I love counting
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<fstream>
#include<ctime>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 100010
#define B 316
#define LOG 17
using namespace std;
inline int read(){
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') s = (s<<3)+(s<<1)+(ch^48), ch = getchar();
return s*w;
}
int num[N], siz[N*LOG];
int cnt = 1;
void insert(int k, int id){
if(!k) return;
if(id == -1 && --num[k] > 0) return;
if(id == 1 && num[k]++ > 0) return;
int x = 1;
siz[x] += id;
per(i,16,0) x = (x<<1) + (k>>i&1), siz[x] += id;
}
int query(int a, int b){
int x = 1, ret = 0;
per(i,16,0){
int dir = (b>>i&1)^(a>>i&1);
if(b>>i&1) ret += siz[(x<<1) + (dir^1)];
x = (x<<1) + dir;
}
ret += siz[x];
return ret;
}
int a[N], ans[N];
int n, q;
struct query{
int l, r, a, b, id;
bool operator < (query k){ return (l/B != k.l/B ? l/B < k.l/B : (r < k.r) ^ ((l/B)&1)); }
} ask[N];
int main(){
n = read();
rep(i,1,n) a[i] = read();
q = read();
rep(i,1,q){
ask[i].l = read(), ask[i].r = read(), ask[i].a = read(), ask[i].b = read();
ask[i].id = i;
}
sort(ask+1, ask+q+1);
int l = 0, r = 0;
rep(i,1,q){
while(l > ask[i].l) insert(a[--l], 1);
while(r < ask[i].r) insert(a[++r], 1);
while(l < ask[i].l) insert(a[l++], -1);
while(r > ask[i].r) insert(a[r--], -1);
ans[ask[i].id] = query(ask[i].a, ask[i].b);
}
rep(i,1,q) printf("%d\n", ans[i]);
return 0;
}Rocket land
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int K=2;
const int N=5e5+10;
const int mod=1e9+7;
const double alpha=0.75;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%mod;a=a*a%mod;n>>=1;}return res;}
int now;
struct Point
{
int num[K],val,id;
Point(){};
Point(int xx,int yy,int vall){
num[0]=xx,num[1]=yy,val=vall;
}
friend bool operator <(Point a,Point b)
{
return a.num[now]<b.num[now];
}
}p[N],p1[N];
struct tree
{
int l,r,siz,minn[K],maxx[K],tf,fa;
ll sum;
int exist;
Point p;
};
struct KDT
{
tree t[N];
int id[N];
int tot,root;
int cnt,rubbish[N];
int cnt1;
ll ans=0;
priority_queue<ll,vector<ll>,greater<ll> >q;
void init()
{
cnt=0,tot=0,cnt1=0,ans=0,root=0;
}
int newnode(){
if(cnt)return rubbish[cnt--];
return ++tot;
}
void up(int u)
{
for(int i=0;i<K;i++){
t[u].minn[i]=t[u].maxx[i]=t[u].p.num[i];
if(t[u].l){
t[u].minn[i]=min(t[u].minn[i],t[t[u].l].minn[i]);
t[u].maxx[i]=max(t[u].maxx[i],t[t[u].l].maxx[i]);
}
if(t[u].r){
t[u].minn[i]=min(t[u].minn[i],t[t[u].r].minn[i]);
t[u].maxx[i]=max(t[u].maxx[i],t[t[u].r].maxx[i]);
}
}
if(t[u].l)t[t[u].l].fa=u;
if(t[u].r)t[t[u].r].fa=u;
t[u].sum=t[t[u].l].sum+t[t[u].r].sum+(t[u].exist?t[u].p.val:0);
t[u].siz=t[t[u].l].siz+t[t[u].r].siz+t[u].exist;
}
void slap(int u)
{
if(!u)return;
if(t[u].exist)p1[++cnt1]=t[u].p;
rubbish[++cnt]=u;
slap(t[u].l);
slap(t[u].r);
}
int rebuild(int l,int r,int d)
{
now=d;
if(l>r)return 0;
int mid=(l+r)>>1,u=newnode();
nth_element(p1+l,p1+mid,p1+r+1);
t[u].p=p1[mid];
t[u].exist=1;
id[p1[mid].id]=u;
t[u].l=rebuild(l,mid-1,(d+1)%K);
t[u].r=rebuild(mid+1,r,(d+1)%K);
up(u);
return u;
}
void check(int &u,int d)
{
if(t[t[u].l].siz>alpha*t[u].siz||t[t[u].r].siz>alpha*t[u].siz){
cnt1=0;
slap(u);
u=rebuild(1,t[u].siz,d);
}
}
void insert(int &u,Point now,int d)
{
if(!u){
u=newnode();
t[u].exist=1;
t[u].l=t[u].r=0,t[u].p=now;
up(u);
return;
}
if(now.num[d]<=t[u].p.num[d])insert(t[u].l,now,(d+1)%K);
else insert(t[u].r,now,(d+1)%K);
up(u);
check(u,d);
}
bool inside(int x1,int y1,int r,int X1,int Y1,int X2,int Y2)
{
int cnt=0;
if(1ll*(X1-x1)*(X1-x1)+1ll*(Y1-y1)*(Y1-y1)<=1ll*r*r)cnt++;
if(1ll*(X2-x1)*(X2-x1)+1ll*(Y1-y1)*(Y1-y1)<=1ll*r*r)cnt++;
if(1ll*(X1-x1)*(X1-x1)+1ll*(Y2-y1)*(Y2-y1)<=1ll*r*r)cnt++;
if(1ll*(X2-x1)*(X2-x1)+1ll*(Y2-y1)*(Y2-y1)<=1ll*r*r)cnt++;
if(cnt==4)return true;
else return false;
}
bool outside(int x1,int y1,int r,int X1,int Y1,int X2,int Y2)
{
int x,y;
if(x1<=X2&&x1>=X1)x=x1;
else if(x1<X1)x=X1;
else x=X2;
if(y1<=Y2&&y1>=Y1)y=y1;
else if(y1<Y1)y=Y1;
else y=Y2;
if(1ll*(x1-x)*(x1-x)+1ll*(y1-y)*(y1-y)<=1ll*r*r)return false;
else return true;
}
ll query(int u,int x1,int y1,int r)
{
if(!u)return 0;
if(t[u].siz==0)return 0;
if(inside(x1,y1,r,t[u].minn[0],t[u].minn[1],t[u].maxx[0],t[u].maxx[1]))return t[u].sum;
if(outside(x1,y1,r,t[u].minn[0],t[u].minn[1],t[u].maxx[0],t[u].maxx[1]))return 0;
ll ans=0;
if(t[u].exist&&inside(x1,y1,r,t[u].p.num[0],t[u].p.num[1],t[u].p.num[0],t[u].p.num[1]))ans+=t[u].p.val;
ans+=query(t[u].l,x1,y1,r)+query(t[u].r,x1,y1,r);
return ans;
}
}T1;
int r[N];
void solve()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&p[i].num[0],&p[i].num[1],&p[i].val,&r[i]);
p[i].id=i;
p1[i]=p[i];
}
T1.init();
for(int i=1;i<=n;i++){
T1.insert(T1.root,p1[i],0);
printf("%lld\n",T1.query(T1.root,p[i].num[0],p[i].num[1],r[i]));
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
solve();
}
}Pass!
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 1e7 + 30;
const int base = 1e9;
const int P = 131;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);
ll hs[N], head[N], nexts[N], id[N], top;
void insert(ll x, ll y, ll mod) //mod传 N
{
ll k = x % mod;
hs[top] = x;
id[top] = y;
nexts[top] = head[k];
head[k] = top++;
}
ll find(ll x, ll mod)
{
ll k = x % mod;
for (int i = head[k]; i != -1; i = nexts[i])
if (hs[i] == x)
return id[i];
return -1;
}
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll BSGS(ll a, ll b, ll p, ll a1) //质数传1
{
memset(head, -1, sizeof(head));
top = 1;
a %= p, b %= p;
if (a1 == 1 && 1 % p == b % p)
return 0;
if (a == 0)
{
if (b == 0)
return 1;
else
return -1;
}
//unordered_map<ll, ll> hash; //map unordered_map 都试试
ll k = sqrt(p) + 1;
ll ak = 1;
for (ll i = 0; i < k; ++i)
{
ll t = ak * b % p;
insert(t, i, N);
//hash[t] = i;
ak = ak * a % p;
}
for (ll i = 0; i <= k; ++i)
{
/* if (hash.count(a1) && i * k - hash[a1] >= 0)
return i * k - hash[a1]; */
ll j = find(a1, N);
if (j != -1 && i * k - j >= 0)
return i * k - j;
a1 = a1 * ak % p;
}
return -1;
}
ll exBSGS(ll a, ll b, ll p)
{
a %= p, b %= p;
if (b == 1 || p == 1)
return 0;
ll cnt = 0, a1 = 1;
ll d = gcd(a, p);
while (d > 1)
{
if (b % d)
return -1;
p /= d;
b /= d;
a1 = (a1 * a / d) % p;
++cnt;
if (b == a1)
return cnt;
d = gcd(a, p);
}
ll res = BSGS(a, b, p, a1);
if (res == -1)
return -1;
else
return res + cnt;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
ll n, x;
scanf("%lld%lld", &n, &x);
ll ans1 = exBSGS((n - 1), n * x + (n - 1), mod);
if (ans1 % 2 == 0 || ans1 == -1)
ans1 = INF;
ll ans2 = exBSGS((n - 1), n * x + (1 - n), mod);
if (ans2 % 2 == 1 || ans2 == -1)
ans2 = INF;
ll ans = min(ans1, ans2);
if (ans == INF)
printf("-1\n");
else
printf("%lld\n", ans);
}
return 0;
}I love exam
#include<iostream>
#include<map>
#include<vector>
#include<cstring>
using namespace std;
#define int long long
int T,n,m,t,p;
map<string,int> mp;
int dp[505][5],f[505];
int ddp[505][5];
struct nd{
int x,y;
};
vector<nd> a[55];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
// int n;
cin>>n;
string s;
mp.clear();
for(int i=1;i<=n;i++){
cin>>s;
mp[s]=i;a[i].clear();
}
cin>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>s>>x>>y;
a[mp[s]].push_back({x,y});
}
cin>>t>>p;
memset(dp,-1,sizeof(dp));
dp[0][0] = 0;
for(int i=1;i<=n;i++){
memset(f,0,sizeof(f));
for(auto s:a[i]){
for(int j=t-s.y;j>=0;j--){
f[j+s.y] = max(f[j+s.y],min((long long)100,f[j]+s.x));
}
}
memset(ddp,-1,sizeof(ddp));
for(int j=0;j<=t;j++){
for(int k=0;k<=p;k++){
if(dp[j][k]==-1)continue;
for(int d=0;d<=t;d++){
int nx=k;
if(f[d]<60)nx=k+1;
if(j+d<=t&&nx<=p){
ddp[j+d][nx]=max(ddp[j+d][nx],dp[j][k]+f[d]);
}
}
}
}
for(int j=0;j<=t;j++){
for(int k=0;k<=p;k++){
dp[j][k]=ddp[j][k];
}
}
}
long long ans=-1;
for(int j=0;j<=t;j++){
for(int k=0;k<=p;k++){
ans=max(ans,ddp[j][k]);
}
}
printf("%lld\n",ans);
}
return 0;
}I love data structure
#include<bits/stdc++.h>
#define N 200009
using namespace std;
typedef long long ll;
#define int long long
const int mod=1e9+7;
ll a[N][2];
int n,m;
inline ll rd(){
ll x=0;char c=getchar();bool f=0;
while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?-x:x;
}
inline void MOD(ll &x){x=x>=mod?x-mod:x;}
struct matrix{
ll a[2][2];
matrix(){memset(a,0,sizeof(a));a[0][0]=a[1][1]=1;}
inline matrix operator *(const matrix &b)const{
matrix c;c.a[0][0]=c.a[1][1]=0;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
MOD(c.a[i][j]+=a[i][k]*b.a[k][j]%mod);
return c;
}
};
inline void clear(matrix &a){
memset(a.a,0,sizeof(a.a));
a.a[0][0]=a.a[1][1]=1;
}
matrix rev,wk;
inline void wok(int cnt,int l,int r,int L,int R,matrix tag);
inline void upd(int cnt,int l,int r,int tag,int L,int R,int x);
struct seg{
ll sum[2],sm,adtag[2],sum1[2];
matrix tag;
}tr[N<<2];
void push_up(int p){
tr[p].sum[0]=(tr[p*2].sum[0]+tr[p*2+1].sum[0])%mod;
tr[p].sum[1]=(tr[p*2].sum[1]+tr[p*2+1].sum[1])%mod;
tr[p].sum1[1]=(tr[p*2].sum1[1]+tr[p*2+1].sum1[1])%mod;
tr[p].sum1[0]=(tr[p*2].sum1[0]+tr[p*2+1].sum1[0])%mod;
tr[p].sm=(tr[p*2].sm+tr[p*2+1].sm)%mod;
}
void build(int cnt,int l,int r){
if(l==r){
tr[cnt].sum[0]=a[l][0];
tr[cnt].sum[1]=a[l][1];
tr[cnt].sum1[0]=a[l][0]*a[l][0]%mod;
tr[cnt].sum1[1]=a[l][1]*a[l][1]%mod;
tr[cnt].sm=a[l][0]*a[l][1]%mod;
return;
}
int mid=(l+r)>>1;
build(cnt*2,l,mid);
build(cnt*2+1,mid+1,r);
push_up(cnt);
}
void push_down(int cnt,int l,int r){
int mid=(l+r)>>1;
wok(cnt<<1,l,mid,l,mid,tr[cnt].tag);
wok(cnt<<1|1,mid+1,r,mid+1,r,tr[cnt].tag);
clear(tr[cnt].tag);
for(int i=0;i<2;i++){
upd(cnt*2,l,mid,i,l,mid,tr[cnt].adtag[i]);
upd(cnt*2+1,mid+1,r,i,mid+1,r,tr[cnt].adtag[i]);
tr[cnt].adtag[i]=0;
}
}
void upd(int cnt,int l,int r,int tag,int L,int R,int x){
if(l>=L&&r<=R){
tr[cnt].adtag[tag]=(tr[cnt].adtag[tag]+x)%mod;
tr[cnt].sum1[tag]=(tr[cnt].sum1[tag]+2*tr[cnt].sum[tag]%mod*x%mod+x*x%mod*(r-l+1)%mod)%mod;
tr[cnt].sum[tag]=(tr[cnt].sum[tag]+(r-l+1)*x%mod)%mod;
tr[cnt].sm=(tr[cnt].sm+x*tr[cnt].sum[tag^1]%mod)%mod;
return;
}
int mid=(l+r)>>1;
push_down(cnt,l,r);
if(L<=mid)upd(cnt*2,l,mid,tag,L,R,x);
if(R>mid)upd(cnt*2+1,mid+1,r,tag,L,R,x);
push_up(cnt);
}
void wok(int cnt,int l,int r,int L,int R,matrix x){
if(l>=L&&r<=R){
ll sm=tr[cnt].sm;
ll c=x.a[0][0],d=x.a[0][1],e=x.a[1][0],f=x.a[1][1];
ll xx=tr[cnt].sum1[0],yy=tr[cnt].sum1[1];
tr[cnt].sm=tr[cnt].sum1[0]*c%mod*d+tr[cnt].sum1[1]*e%mod*f+tr[cnt].sm*(c*f%mod+d*e%mod);
tr[cnt].sm=tr[cnt].sm%mod;
tr[cnt].sum1[0]=(c*c%mod*xx+e*e%mod*yy+2ll*c*e%mod*sm)%mod;
tr[cnt].sum1[1]=(d*d%mod*xx+f*f%mod*yy+2ll*d*f%mod*sm)%mod;
xx=tr[cnt].sum[0];yy=tr[cnt].sum[1];
tr[cnt].sum[0]=(xx*c+yy*e)%mod;
tr[cnt].sum[1]=(xx*d+yy*f)%mod;
xx=tr[cnt].adtag[0];yy=tr[cnt].adtag[1];
tr[cnt].adtag[0]=(xx*x.a[0][0]+yy*x.a[1][0])%mod;
tr[cnt].adtag[1]=(xx*x.a[0][1]+yy*x.a[1][1])%mod;
tr[cnt].tag=tr[cnt].tag*x;
return;
}
int mid=(l+r)>>1;
push_down(cnt,l,r);
if(mid>=L)wok(cnt<<1,l,mid,L,R,x);
if(mid<R)wok(cnt<<1|1,mid+1,r,L,R,x);
push_up(cnt);
}
long long q(int cnt,int l,int r,int L,int R){
if(L<=l&&r<=R){
return tr[cnt].sm;
}
int ans=0;
int mid=(l+r)>>1;
push_down(cnt,l,r);
if(L<=mid)ans=q(cnt*2,l,mid,L,R);
if(R>mid)ans=(ans+q(cnt*2+1,mid+1,r,L,R))%mod;
return ans;
}
signed main(){
//int n;
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i][0],&a[i][1]);
build(1,1,n);
// int m;
cin>>m;
int l,r,tag,x,opt;
while(m--){
wk.a[0][0]=wk.a[0][1]=3;
wk.a[1][0]=2;
wk.a[1][1]=mod-2;
rev.a[0][0]=rev.a[1][1]=0;
rev.a[0][1]=rev.a[1][0]=1;
scanf("%lld",&opt);
if(opt==1){
//A int tag,l,r,x;
scanf("%lld%lld%lld%lld",&tag,&l,&r,&x);
upd(1,1,n,tag,l,r,x);
}
else if(opt==2){
scanf("%lld%lld",&l,&r);
wok(1,1,n,l,r,wk);
}
else if(opt==3){
// int l,r,x;
scanf("%lld%lld",&l,&r);
wok(1,1,n,l,r,rev);
}else if(opt==4){
// int l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",q(1,1,n,l,r));
}
}
return 0;
}I love max and multiply
#include<bits/stdc++.h>
#define ll long long
const double pi = acos(-1);
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
const int mod = 998244353;
const int N = 1e6+5;
int a[N],b[N];
ll mxa[N],mxb[N],mna[N],mnb[N];
signed main(){
int T;
scanf("%lld",&T);
while(T--){
int n;
scanf("%lld",&n);
ll ans = 0;
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
for(int j=0;j<n;j++) scanf("%lld",&b[j]);
ll mx = -inf;
for(int i=n-1;i>=0;i--){
mxa[i]=mna[i]=a[i];
mxb[i]=mnb[i]=b[i];
for(int j=0;j<=18;j++){
if(((i>>j)&1)==0){
int x=i+(1<<j);
if(x>=n)continue;
mxa[i]=max(mxa[i],mxa[x]);
mna[i]=min(mna[i],mna[x]);
mxb[i]=max(mxb[i],mxb[x]);
mnb[i]=min(mnb[i],mnb[x]);
}
}
if(i==n-1)mx=(long long)a[i]*b[i];
mx=max(mx,max(max(mxa[i]*mxb[i],mxa[i]*mnb[i]),max(mna[i]*mxb[i],mna[i]*mnb[i])));
ans+=mx;
ans%=mod;
}
ans = (ans%mod + mod)%mod;
printf("%lld\n",ans%mod);
}
return 0;
}zoto
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e5+10;
int T,n,m,k,a[maxn],len;
struct Node{
int l,r,id;
int u,v;
bool operator<(const Node &x) const {
if (l /len!= x.l /len) return l < x.l;
return (l /len) & 1 ? r < x.r : r > x.r;
}
}node[maxn];
bool cmp(Node x,Node y){
if(x.l/len==y.l/len)
return x.r<y.r;
return x.l<y.l;
}
int ans1[maxn];
int num[maxn],cnt[maxn];
void add(int x){
if(num[x]==0){
num[x]++;
cnt[x/len]++;
}
else{
num[x]++;
}
}
void del(int x){
num[x]--;
if(num[x]==0){
cnt[x/len]--;
}
}
int cal(int x){
int sum=0;
for(int i=0;i<x/len;i++){
sum+=cnt[i];
}
for(int i=(x/len)*len;i<=x;i++){
sum+=(num[i]>0);
}
return sum;
}
int main(){
int t;
cin>>t;
while(t--){
memset(num,0,sizeof(num));
memset(cnt,0,sizeof(cnt));
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&node[i].l,&node[i].u,&node[i].r,&node[i].v);
node[i].id=i;
}
len=sqrt(n);
sort(node+1,node+1+m);
for(int i=1,l=1,r=0;i<=m;i++){
while(l>node[i].l){
add(a[--l]);
}
while(r<node[i].r){
add(a[++r]);
}
while(l<node[i].l){
del(a[l++]);
}
while(r>node[i].r){
del(a[r--]);
}
ans1[node[i].id]=cal(node[i].v)-cal(node[i].u-1);
}
for(int i=1;i<=m;i++){
printf("%lld\n",ans1[i]);
}
}
}KD-Graph
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1e6+10;
int T,n,m,k,fa[maxn],now,ans;
struct da{int u,v,w;}q[maxn];
bool cmp(da aa,da bb){return aa.w<bb.w;}
int getf(int x)
{
if (fa[x]==x) return x;
fa[x]=getf(fa[x]);
return fa[x];
}
void solve()
{
scanf("%d%d%d",&n,&m,&k); now=n; ans=0;
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=m;i++) scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);
sort(q+1,q+m+1,cmp);
for (int i=1;i<=m;i++)
{
if (q[i].w!=q[i-1].w){
if (now==k) {printf("%d\n",ans); return;}
}
if (getf(q[i].u)==getf(q[i].v)) continue;
now--; fa[getf(q[i].u)]=getf(q[i].v); ans=q[i].w;
}
printf("%d\n",now==k?ans:-1);
}
int main()
{
scanf("%d",&T);
while (T--) solve();
return 0;
}Xor sum
#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int inf=1e9;
const int N=1e5+10;
const int M=3e6+10;
const int mo=998244353;
int p[M][2],mx[M],a[N];
void sol(){
int n,k;
scanf("%d%d",&n,&k);
rep(i,1,n){
scanf("%d",&a[i]);
a[i]^=a[i-1];
}
int anl=-1,anr=n,tot=1;
mx[1]=-1;
p[1][0]=p[1][1]=0;
rep(i,1,n){
int x=1,res=-1;
dep(j,29,0){
int w=(a[i]>>j)&1;
if(!((k>>j)&1)){
if(p[x][w^1])res=max(res,mx[p[x][w^1]]);
x=p[x][w];
}else x=p[x][w^1];
if(!x)break;
}
if(x)res=max(res,mx[x]);
if(res>=0&&i-res<anr-anl)anl=res,anr=i;
x=1;
dep(j,29,0){
int w=(a[i]>>j)&1;
if(!p[x][w]){
p[x][w]=++tot;mx[tot]=-1;
p[tot][0]=p[tot][1]=0;
}
x=p[x][w];
mx[x]=max(mx[x],i);
}
}
if(anl>=0)printf("%d %d\n",anl+1,anr);
else printf("-1\n");
}
int main(){
int t;
scanf("%d",&t);
rep(i,1,t)sol();
}
投递谷歌等公司10个岗位 >
