莫队
woshishei
·
·
个人记录
[SDOI2009]HH的项链
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define debug printf("\n-------------\n")
using namespace std;
typedef long long ll;
const int INF1=(~0u>>2);
const ll INF2=(~0ull>>2),P1=10007,P2=998244353,P3=1000000007;
int n,m,b,a[1000010],pos[1000010],ans[1000010],cnt[1000010],sum=0;
struct node
{
int l,r,id;
bool operator <(const node &R)const
{
return pos[l]!=pos[R.l]?(pos[l]<pos[R.l]):(r<R.r);
}
}q[1000010];
void upd(int p,int f)
{
cnt[a[p]]+=f;
if(f==1&&cnt[a[p]]==1)
sum++;
if(f==-1&&cnt[a[p]]==0)
sum--;
}
int main()
{
scanf("%d",&n);
b=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pos[i]=i/b;
}
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q,q+m);
int l=1,r=0;
for(int i=0;i<m;i++)
{
while(r<q[i].r)upd(++r,1);
while(r>q[i].r)upd(r--,-1);
while(l<q[i].l)upd(l++,-1);
while(l>q[i].l)upd(--l,1);
ans[q[i].id]=sum;
}
for(int i=0;i<m;i++)
printf("%d\n",ans[i]);
return 0;
}
[国家集训队]小Z的袜子
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define debug printf("\n-------------\n")
using namespace std;
typedef long long ll;
const int INF1=(~0u>>2);
const ll INF2=(~0ull>>2),P1=10007,P2=998244353,P3=1000000007;
int n,m,b,a[1000010],pos[1000010],ans[1000010][2];
ll sum=0,cnt[1000010];
struct node
{
int l,r,id;
bool operator <(const node &R)const
{
return pos[l]!=pos[R.l]?(pos[l]<pos[R.l]):(r<R.r);
}
}q[1000010];
void upd(int p,int f)
{
sum-=cnt[a[p]]*(cnt[a[p]]-1);
cnt[a[p]]+=f;
sum+=cnt[a[p]]*(cnt[a[p]]-1);
}
ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
int main()
{
scanf("%d %d",&n,&m);
b=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pos[i]=i/b;
}
for(int i=0;i<m;i++)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q,q+m);
int l=1,r=0;
for(int i=0;i<m;i++)
{
while(r<q[i].r)upd(++r,1);
while(r>q[i].r)upd(r--,-1);
while(l<q[i].l)upd(l++,-1);
while(l>q[i].l)upd(--l,1);
if(q[i].l==q[i].r)
{
ans[q[i].id][0]=0;
ans[q[i].id][1]=1;
continue;
}
ll len=q[i].r-q[i].l+1;
ll d=gcd(sum,len*(len-1));
ans[q[i].id][0]=sum/d;
ans[q[i].id][1]=len*(len-1)/d;
}
for(int i=0;i<m;i++)
printf("%lld/%lld\n",ans[i][0],ans[i][1]);
return 0;
}
大爷的字符串题
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define debug printf("\n-------------\n")
using namespace std;
typedef long long ll;
const int INF1=(~0u>>2);
const ll INF2=(~0ull>>2),P1=10007,P2=998244353,P3=1000000007;
int n,m,b,a[200010],c[200010],pos[200010],ans[200010],cnt[200010],num[200010],mx;
struct node
{
int l,r,id;
bool operator <(const node &R)const
{
return pos[l]==pos[R.l]?(r<R.r):pos[l]<pos[R.l];
}
}q[200010];
void upd(int p,int f)
{
if(f==1)
{
num[cnt[a[p]]]--;
cnt[a[p]]++;
num[cnt[a[p]]]++;
mx=max(mx,cnt[a[p]]);
}
else
{
num[cnt[a[p]]]--;
if(mx==cnt[a[p]]&&num[cnt[a[p]]]==0)
mx--;
cnt[a[p]]--;
num[cnt[a[p]]]++;
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memcpy(c,a,sizeof(a));
sort(c+1,c+n+1);
for(int i=1;i<=n;i++)
a[i]=lower_bound(c+1,c+n+1,a[i])-c;
b=sqrt(m);
for(int i=0;i<m;i++)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].id=i;
pos[i]=i/b;
}
sort(q,q+m);
int l=1,r=0;
for(int i=0;i<m;i++)
{
while(r<q[i].r)upd(++r,1);
while(r>q[i].r)upd(r--,-1);
while(l<q[i].l)upd(l++,-1);
while(l>q[i].l)upd(--l,1);
ans[q[i].id]=-mx;
}
for(int i=0;i<m;i++)
printf("%d\n",ans[i]);
return 0;
}
[CQOI2018]异或序列
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define debug printf("\n-------------\n")
using namespace std;
typedef long long ll;
const int INF1=(~0u>>2);
const ll INF2=(~0ull>>2),P1=10007,P2=998244353,P3=1000000007;
int n,m,b,k,a[100010],pos[100010],ans[100010],sum=0,cnt[100010];
struct node
{
int l,r,id;
bool operator <(const node &R)const
{
return pos[l]!=pos[R.l]?(pos[l]<pos[R.l]):(r<R.r);
}
}q[100010];
void upd(int p,int f)
{
sum-=(ll)cnt[a[p]]*cnt[a[p]^k];
cnt[a[p]]+=f;
sum+=(ll)cnt[a[p]]*cnt[a[p]^k];
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
b=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]^=a[i-1];
pos[i]=i/b;
}
for(int i=0;i<m;i++)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].l--;
q[i].id=i;
}
sort(q,q+m);
int l=1,r=0;
for(int i=0;i<m;i++)
{
while(r<q[i].r)upd(++r,1);
while(r>q[i].r)upd(r--,-1);
while(l<q[i].l)upd(l++,-1);
while(l>q[i].l)upd(--l,1);
ans[q[i].id]=sum;
}
for(int i=0;i<m;i++)
printf("%d\n",ans[i]);
return 0;
}
[AHOI2013]作业
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define debug printf("\n-------------\n")
using namespace std;
typedef long long ll;
const int INF1=(~0u>>2);
const ll INF2=(~0ull>>2),P1=10007,P2=998244353,P3=1000000007;
int n,m,b,a[100010],c[100010],pos[100010],ans[100010][2],tree[2][100010],cnt[100010],sum=0;
struct node
{
int l,r,id,a,b;
bool operator <(const node &R)const
{
return pos[l]!=pos[R.l]?(pos[l]<pos[R.l]):(r<R.r);
}
}q[100010];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int k,int f)
{
while(x<=n)
{
tree[f][x]+=k;
x+=lowbit(x);
}
}
int query(int x,int f)
{
int res=0;
while(x>=1)
{
res+=tree[f][x];
x-=lowbit(x);
}
return res;
}
void upd(int p,int f)
{
if(cnt[a[p]]==0)
add(a[p],1,1);
cnt[a[p]]+=f;
add(a[p],f,0);
if(cnt[a[p]]==0)
add(a[p],-1,1);
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
b=sqrt(n);
for(int i=0;i<m;i++)
{
scanf("%d %d %d %d",&q[i].l,&q[i].r,&q[i].a,&q[i].b);
q[i].id=i;
pos[i]=i/b;
}
sort(q,q+m);
int l=1,r=0;
for(int i=0;i<m;i++)
{
while(r<q[i].r)upd(++r,1);
while(r>q[i].r)upd(r--,-1);
while(l<q[i].l)upd(l++,-1);
while(l>q[i].l)upd(--l,1);
ans[q[i].id][0]=query(q[i].b,0)-query(q[i].a-1,0);
ans[q[i].id][1]=query(q[i].b,1)-query(q[i].a-1,1);
}
for(int i=0;i<m;i++)
printf("%d %d\n",ans[i][0],ans[i][1]);
return 0;
}