A 区间不同个数的多少
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 1000005
int n,m;
struct Node{
int a;int b;
int id;
}node[N];
int num[N];
int block;
bool cmp(struct Node a,struct Node b){
if((a.a/block)==(b.a/block)){
return a.b<b.b;
}
return (a.a/block)<(b.a/block);
}
int ans[N];
int vis[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&num[i]);
}
scanf("%d",&m);
block=sqrt(n+0.5);
for(int i=1;i<=m;i++){
scanf("%d%d",&node[i].a,&node[i].b);
node[i].id=i;
}
sort(node+1,node+1+m,cmp);
int l,r;
l=1;r=0;
int t=0;
for(int i=1;i<=m;i++){
while(l<node[i].a){
vis[num[l]]--;
if(vis[num[l]]==0)
t--;
l++;
}
while(l>node[i].a){
l--;
vis[num[l]]++;
if(vis[num[l]]==1)
t++;
}
while(r<node[i].b){
r++;
vis[num[r]]++;
if(vis[num[r]]==1)
t++;
}
while(r>node[i].b){
vis[num[r]]--;
if(vis[num[r]]==0)
t--;
r--;
}
ans[node[i].id]=t;
}
for(int i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
return 0;
}
因为没有快速读入 超时了。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
using namespace std;
#define N 1000005
typedef long long ll;
struct Node{
int a,b,k,id;}node[N];
vector<int>v[N];
int n,m;
int num[N];
int cn[N];
int en[N];
int block;
int c[N];
int mun[N];
int po[N];
int nn=1;
bool vis[N];
int nnum[N];
void add(int x){
cn[mun[x]]++;
c[cn[mun[x]]]++;
}
void del(int x){
c[cn[mun[x]]]--;
cn[mun[x]]--;
}
bool cmp(struct Node a,struct Node b){
if(a.a/block==b.a/block)
return a.b<b.b;
return a.a/block<b.a/block;
}
int pb[N];
int dfs(int x){
mun[nn]=num[x];
po[x]=nn;
nn++;
vis[x]=1;
nnum[x]=1;
for(int i=0;i<v[x].size();i++){
if(vis[v[x][i]]==0){
nnum[x]+=dfs(v[x][i]);
}
}
pb[x]=nn-1;
return nnum[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n+1;i++){
scanf("%d",num+i);
}
int u,vv;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&vv);
v[u].push_back(vv);
v[vv].push_back(u);
}
dfs(1);
for(int i=1;i<=m;i++){
scanf("%d%d",&node[i].a,&node[i].k);
node[i].b=pb[node[i].a];
node[i].a=po[node[i].a];
node[i].id=i;
}
block=sqrt(n+0.5);
sort(node+1,node+1+m,cmp);
int l,r;l=1;r=0;
// for(int i=1;i<nn;i++){
// cout<<mun[i]<<" ";
// }
// cout<<endl;
for(int i=1;i<=m;i++){
// cout<<node[i].a<<" "<<node[i].b<<endl;
while(l<node[i].a){
del(l);l++;
}while(l>node[i].a){
l--;
add(l);
} while(r<node[i].b){
r++;
add(r);
}while(r>node[i].b){
del(r);
r--;
}
en[node[i].id]=c[node[i].k];
}
for(int i=1;i<m+1;i++){
printf("%d\n",en[i]);
}
return 0;
}
没有强制转换成long long wa了2小时，心口子痛 T T ,以后一定不要犯了
求区间的组合数
I
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
#define N 100005
typedef long long ll;
struct Node{
int a,b,id;}node[N];
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
int num[N];
int cn[N];
ll ans=0;
ll en[N];
ll ff[N];
int n,m;
void add(int x){
cn[num[x]]++;
if(cn[num[x]]>1){
ans+=cn[num[x]]-1;
}
}
void del(int x){
if(cn[num[x]]>1)
{
ans-=cn[num[x]]-1;
}
cn[num[x]]--;
}
int block;
bool cmp(struct Node a,struct Node b){
if(a.a/block==b.a/block){
return a.b<b.b;
}
return a.a/block<b.a/block;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n+1;i++){
scanf("%d",num+i);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&node[i].a,&node[i].b);
node[i].id=i;
}
block=sqrt(n+0.5);
sort(node+1,node+1+m,cmp);
int l,r;l=1;r=0;
for(int i=1;i<=m;i++){
while(l<node[i].a){
del(l);l++;
}while(l>node[i].a){
l--;
add(l);
} while(r<node[i].b){
r++;
add(r);
}while(r>node[i].b){
del(r);
r--;
}
en[node[i].id]=ans;
ff[node[i].id]=ll(node[i].b-node[i].a+1)*(node[i].b-node[i].a)/2;
}
for(int i=1;i<m+1;i++){
if(en[i]==0){
printf("0/1\n");
}else{
ll temp=gcd(en[i],ff[i]);
printf("%lld/%lld\n",en[i]/temp,ff[i]/temp);
}
}
return 0;
}
