HNOI 2016 乱做

4542: [Hnoi2016]大数

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 488 Solved: 182
[Submit][Status][Discuss]

Description

　　小 B 有一个很大的数 S，长度达到了 N 位；这个数可以看成是一个串，它可能有前导 0，例如00009312345
。小B还有一个素数P。现在，小 B 提出了 M 个询问，每个询问求 S 的一个子串中有多少子串是 P 的倍数（0 也
是P 的倍数）。例如 S为0077时，其子串 007有6个子串：0,0,7,00,07,007；显然0077的子串007有6个子串都是素
数7的倍数。

Input

　　第一行一个整数：P。第二行一个串：S。第三行一个整数：M。接下来M行，每行两个整数 fr,to，表示对S 的
子串S[fr…to]的一次询问。注意：S的最左端的数字的位置序号为 1；例如S为213567，则S[1]为 2，S[1…3]为 2
13。N,M<=100000，P为素数

Output

　　输出M行，每行一个整数，第 i行是第 i个询问的答案。

Sample Input

11
121121
3
1 6
1 5
1 4

Sample Output

5
3
2
//第一个询问问的是整个串，满足条件的子串分别有：121121,2112,11,121,121。

HINT

2016.4.19新加数据一组

Source

挺可做的一道题，因为P为素数，所以预处理后缀和，答案就是l到r中后缀和相同的数，然后就用莫队搞一搞就行了，（2和5要特判，它只和末位相关）

  1 //start:   finish:
  2 #include<bits/stdc++.h>
  3 #define maxn 100005
  4 using namespace std;
  5 int P;
  6 int a[maxn];
  7 int b[maxn];
  8 long long c[maxn];
  9 int d[maxn];
 10 char s[maxn];
 11 int u[maxn];
 12 struct node
 13 {
 14     int x,y;
 15     int id;
 16     int kuai;
 17 }q[maxn];
 18 int m;
 19 int ge[maxn];
 20 bool cmp(node a,node b)
 21 {
 22     if(a.kuai!=b.kuai)return a.kuai<b.kuai;
 23     else return a.y<b.y;
 24 }
 25 long long res[maxn];
 26 int n;
 27 long long ans=0;
 28 void insert(int x)
 29 {
 30 //    cout<<x<<endl;
 31     ans+=ge[x];
 32     ge[x]++;
 33     //cout<<ans<<" "<<mp[x]<<endl;
 34 }
 35 void del(int x)
 36 {
 37     ge[x]--;
 38     ans-=ge[x];
 39 }
 40 void solve()
 41 {
 42     for(int i=1;i<=n;i++)
 43     {
 44         if((s[i]-'0')%P==0)
 45         {
 46             c[i]=i;
 47             d[i]=1;
 48         }
 49     }
 50     for(int i=1;i<=n;i++)
 51     {
 52         c[i]=c[i-1]+c[i];
 53         d[i]=d[i-1]+d[i];
 54     }
 55     scanf("%d",&m);
 56     for(int i=1;i<=m;i++)
 57     {
 58         int l,r;
 59         scanf("%d%d",&l,&r);
 60         printf("%lld
",c[r]-c[l-1]-1ll*(l-1)*(d[r]-d[l-1]));
 61     }
 62 }
 63 int main()
 64 {
 65     scanf("%d",&P);
 66     scanf("%s",s+1);
 67     n=strlen(s+1);
 68     if(P==2 || P==5)
 69     {
 70         solve();
 71         return 0;
 72     }
 73     scanf("%d",&m);
 74     for(int i=1;i<=m;i++)
 75     {
 76         scanf("%d%d",&q[i].x,&q[i].y);
 77         q[i].kuai=q[i].x/500;
 78         q[i].y++;
 79         q[i].id=i;
 80     }
 81     b[0]=1;
 82     for(int i=1;i<=n;i++)
 83     {
 84         b[i]=1ll*b[i-1]*10%P;
 85     }
 86     for(int i=n;i>=1;i--)
 87     {
 88         a[i]=(1ll*b[n-i]*(s[i]-'0')%P+a[i+1])%P;
 89         u[i]=a[i];
 90     //    cout<<a[i]<<endl;
 91     }
 92     u[n+1]=0;
 93     sort(u+1,u+n+2);
 94     int cx=unique(u+1,u+n+2)-u-1;
 95     for(int i=1;i<=n+1;i++)
 96     {
 97         a[i]=lower_bound(u+1,u+cx+1,a[i])-u;
 98     }
 99     sort(q+1,q+m+1,cmp);
100     int l=1,r=0;
101     for(int i=1;i<=m;i++)
102     {
103     //    cout<<"fffff"<<endl;
104         //cout<<q[i].x<<" "<<q[i].y<<endl;
105         while(r<q[i].y)insert(a[++r]);
106         while(r>q[i].y)del(a[r--]);
107         while(l<q[i].x)del(a[l++]);
108         while(l>q[i].x)insert(a[--l]);
109         res[q[i].id]=ans;
110     }
111     for(int i=1;i<=m;i++)
112     printf("%lld
",res[i]);
113     return 0;
114 }
115 /*
116 11 
117 121121 
118 3 
119 1 6 
120 1 5 
121 1 4 
122 */

View Code

4540: [Hnoi2016]序列

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 328 Solved: 167
[Submit][Status][Discuss]

Description

　　给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：a_l,a_l+1,…,a_r-
1,a_r。若1≤l≤s≤t≤r≤n，则称a[s:t]是a[l:r]的子序列。现在有q个询问，每个询问给定两个数l和r，1≤l≤r
≤n，求a[l:r]的不同子序列的最小值之和。例如，给定序列5,2,4,1,3，询问给定的两个数为1和3，那么a[1:3]有
6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这6个子序列的最小值之和为5+2+4+2+2+2=17。

Input

　　输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开
,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。

Output

　　对于每次询问，输出一行，代表询问的答案。

Sample Input

5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5

Sample Output

28
17
11
11
17

HINT

1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9

Source

又是一道离线题，考虑新加进来一个数的影响，它的影响范围一直到该区间内的最小数为止，然后用前缀和预处理影响值，用st表预处理区间最小值

  1 //start:   finish:
  2 #include<bits/stdc++.h>
  3 #define maxn 100005
  4 using namespace std;
  5 int n,m;
  6 struct node
  7 {
  8     int kuai;
  9     int x,y;
 10     int id;
 11 }q[maxn];
 12 int a[maxn];
 13 bool cmp(node a,node b)
 14 {
 15     if(a.kuai!=b.kuai)return a.kuai<b.kuai;
 16     return a.y<b.y;
 17 }
 18 long long ans;
 19 long long res[maxn];
 20 int st[maxn][30];
 21 int qq[maxn];
 22 int ls1[maxn],ls2[maxn];
 23 long long sum1[maxn],sum2[maxn];
 24 int pos[maxn];
 25 int Log[maxn];
 26 bool ying(int x,int y)
 27 {
 28     return a[x]<a[y];
 29 }
 30 void mengtinghui()
 31 {
 32     set <int> s;
 33     s.insert(0);s.insert(n+1);
 34     for(int i=1;i<=n;i++)pos[i]=i;
 35     sort(pos+1,pos+n+1,ying);
 36     for(int i=1;i<=n;i++)
 37     {
 38         set <int> :: iterator it=s.lower_bound(pos[i]);
 39         ls2[pos[i]]=(*it);
 40         it--;
 41         ls1[pos[i]]=(*it);
 42         s.insert(pos[i]);
 43     }
 44     for(int i=1;i<=n;i++)
 45     {
 46         sum1[i]=sum1[ls1[i]]+1ll*(i-ls1[i])*a[i];
 47 //        cout<<i<<" "<<sum1[i]<<endl;
 48     }
 49     for(int i=n;i>=1;i--)
 50     {
 51         sum2[i]=sum2[ls2[i]]+1ll*(ls2[i]-i)*a[i];
 52     }
 53 }
 54 void yinggua()
 55 {
 56     Log[1]=0;
 57     for(int i=2;i<=n;i++)
 58     {
 59         Log[i]=Log[i/2]+1;
 60         //cout<<"log"<<i<<" "<<Log[i]<<endl;
 61     }
 62     for(int i=1;i<=n;i++)st[i][0]=i;
 63     for(int j=1;j<=20;j++)
 64     {
 65         for(int i=1;i<=n;i++)
 66         {
 67             if(i+(1<<(j-1))>n || a[st[i][j-1]]<a[st[i+(1<<(j-1))][j-1]])
 68             {
 69                 st[i][j]=st[i][j-1];
 70             }
 71             else
 72             {
 73                 st[i][j]=st[i+(1<<(j-1))][j-1];
 74             }
 75         }
 76     }
 77 }
 78 int get(int x,int y)
 79 {
 80     int p=Log[y-x+1];
 81 //    cout<<x<<" "<<y<<" "<<p<<endl;
 82     int u=st[x][p];
 83     int v=st[y-(1<<p)+1][p];
 84     //cout<<x<<" "<<y<<" "<<u<<" "<<v<<" "<<p<<endl;
 85     if(a[u]<a[v])return u;
 86     return v;
 87 }
 88 void insert2(int x,int y,int cheng)
 89 {
 90 //    cout<<"you"<<x<<" "<<y<<" "<<cheng<<endl;
 91     int p=get(x,y);
 92 //    cout<<x<<" "<<y<<" "<<p<<endl;
 93     ans+=1ll*cheng*(sum1[y]-sum1[p]);
 94     ans+=1ll*cheng*(p-x+1)*a[p];
 95 }
 96 void insert1(int x,int y,int cheng)
 97 {
 98 //    cout<<"zuo"<<x<<" "<<y<<" "<<cheng<<endl;
 99     int p=get(x,y);
100     ans+=1ll*cheng*(sum2[x]-sum2[p]);
101 //    cout<<ans<<" "<<sum2[x]<<" "<<sum2[p]<<endl;
102     ans+=1ll*cheng*(y-p+1)*a[p];
103 }
104 int main()
105 {
106     scanf("%d%d",&n,&m);
107     for(int i=1;i<=n;i++)
108     scanf("%d",&a[i]);
109     for(int i=1;i<=m;i++)
110     {
111         scanf("%d%d",&q[i].x,&q[i].y);
112         q[i].id=i;
113         q[i].kuai=q[i].x/500;
114     }
115     mengtinghui();
116     yinggua();
117     sort(q+1,q+m+1,cmp);
118     int l=1,r=0;
119     for(int i=1;i<=m;i++)
120     {
121     //    cout<<"-----"<<q[i].x<<" "<<q[i].y<<endl;
122         while(r<q[i].y)insert2(l,++r,1);
123     //    cout<<ans<<endl; 
124         while(r>q[i].y)insert2(l,r--,-1);
125     //    cout<<ans<<endl;
126         while(l<q[i].x)insert1(l++,r,-1);
127     //    cout<<ans<<endl;
128         while(l>q[i].x)insert1(--l,r,1);
129 //        cout<<ans<<endl;
130         res[q[i].id]=ans;
131 //        cout<<ans<<endl;
132     }
133     for(int i=1;i<=m;i++)
134     printf("%lld
",res[i]);
135     return 0;
136 }
137 /*
138 5 5 
139 5 2 4 1 3 
140 1 5 
141 1 3 
142 2 4 
143 3 5 
144 2 5 
145 */

View Code