Description

Input

Output

Sample Input

10 5
8>6<2<>54<
4 7
1 10
4 4
2 9
8 10

Sample Output

0 0 0 0 0 0 0 0 0 0
4 4 4 3 3 2 1 1 1 0
0 0 0 0 0 0 0 0 0 0
2 2 2 1 2 2 1 0 0 0
0 0 0 1 2 1 0 0 0 0

Data Constraint

Solution

• 我們考慮把這么多的詢問區間一次性處理完。

• 可以在序列最左端添上足夠多的“>”，就能保證最后指針在序列右端出來了。

• 于是我們就直接模擬一遍，統計出到每個位置的時間戳。

• 對于刪除的操作就用一個左右指針維護即可。

• 之后算出每個詢問左端點的時間和最早出這個區間的時間（比如用一個set）。

• 再通過答案的前綴和算出這個時間差的答案即可。

• 時間復雜度大致為 O(10?N) 。

Code

#include<cstdio> #include<cstring> #include<set> #include<cctype> using namespace std; const int N=2e5+5,K=10,inf=1e9; int tot; int l[N],r[N],t[N],pre[N],ans[N*K][K]; char s[N]; set<int>f[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int min(int x,int y) {return x<y?x:y; } int main() {int n=read(),q=read();scanf("%s",s+1);s[0]='#';for(int i=0;i<=n;i++) l[i]=i-1,r[i]=i+1;int x=0,fx=1;while(x<=n){int last=x;x=fx?r[x]:l[x];tot++;f[x].insert(tot);memcpy(ans[tot],ans[tot-1],sizeof(ans[tot]));if(!t[x]) t[x]=tot,pre[x]=l[x];if(isdigit(s[x])){ans[tot][s[x]-'0']++;if(s[x]=='0'){l[r[x]]=l[x];r[l[x]]=r[x];if(t[x]==tot) pre[x]=l[x];}else s[x]--;}else{if(!isdigit(s[last]) && s[last]^'#'){l[r[last]]=l[last];r[l[last]]=r[last];if(t[x]==tot) pre[x]=l[x];}fx=s[x]=='<'?0:1;}}while(q--){int x=read(),y=read();set<int>::iterator it=f[pre[x]].lower_bound(t[x]);int t1=it==f[pre[x]].end()?inf:*it,t2=t[x]-1;t1=min(t1,t[y+1])-1;for(int i=0;i<=9;i++) write(ans[t1][i]-ans[t2][i]),putchar(' ');putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5623. 【NOI2018模拟4.2】program的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。