SWAG(Sliding Window Aggregation)ã®å®è£ ã«ã¤ãã¦ã®ææ¡
注æ
æ¬è¨äºã¯çè
ãæè¥æ°ã®ãããã§æ¸ããè¨äºã§ããæç¨æ§ããªãããã§ããªãã®ã§ãèªããªã¨ã¾ã§ã¯è¨ãã¾ããããæ°ãã«æ¸ãç´ããè¨äºãåããã¦ã覧ãã ããã
motsu-xe.hatenablog.com
注æçµãã
ããããããããããããããããããã
ãã¯ãããããã¾ãããã®æ¥çã§ã¯ä½æã§ããã¯ãããããã¾ããæ¨æ¶ã§ãã
ä»åã¯å°ãåã«Twitterã§ãã®è©±é¡æã¡ããã«ãªã£ã¦ãããSWAGã«ã¤ãã¦ã®ã話ããããã¨æãã¾ããã¨ã¯ããç§ã¯ãã¼ã¿æ§é ã«é è©£ãæ·±ãããã§ã¯ãªãã®ã§ããã¾ãæ·±ãã«çªã£è¾¼ããã¨ã¯ã§ãã¾ãããä¸å¿ç´¹ä»ã¯ãã¾ããã飽ãã¾ã§ãå®ç¨çãªå®è£ ã®è©±ããããã ããªã®ã§ã詳ããã¯ä»ã®æ¹ã®è¨äºãã覧ãã ããã
SWAGã¨ã¯
ã¹ã©ã¤ãæå°å¤ãç¥ã£ã¦ãã¾ããï¼ããå¶ç´ãæºãããè¤æ°ã®åºéã«å¯¾ãã¦ããã®åºéæå°å¤ãæ±ããé«éã«æ±ãããã¼ã¿æ§é ã§ãã詳ããã¯ã°ã°ã£ã¦æ¬²ããã®ã§ãããç°¡åã«è¨ãã¨ä»¥ä¸ã«ç¤ºãéãã§ãã
å ¨é åºéåã®è¦ç´ ã®é åãä¸ãããããåã®åºéã§ã®é åè¦ç´ ã®æå°å¤ãæ±ããããã®æä½å ¨ä½ãã§è¡ãããã ãåºéåã¯ãæºããã¦ããå¿ è¦ãããã
å°ºåãã®ããã«åºéã®å·¦ç«¯ã¨å³ç«¯ãã¹ã©ã¤ããããªãããæå°å¤ãæ±ããã®ã§ã¹ã©ã¤ãæå°å¤ã¨å¼ã°ãã¾ãã
SWAGã¨è¨ãã®ã¯å¯è½ãªæä½ã ããè¦ãã°ãã¹ã©ã¤ãæå°å¤ã®å®å
¨ä¸ä½äºæã®ãã¼ã¿æ§é ã§ããå
¨é åºéåã«ãããæ¼ç®ã«ã¤ãã¦åºéã§ã®æ¼ç®çµæãè¿ãã®ãã¹ã©ã¤ãæå°å¤ãªã®ã«å¯¾ããã¢ãã¤ãã«ãããæ¼ç®ã«ã¤ãã¦åºéã§ã®æ¼ç®çµæãè¿ãã®ãSWAGã§ããä¸è¬ã«å
¨é åºéåã«ã§æ¼ç®ãå
¥ãããã®ã¯ã¢ãã¤ãã«ãªã*1ã®ã§ãä¸è¬åã«ãªã£ã¦ãããã¨ããããã¾ããä¸å¿è¦ä»¶ãæ´çãã¦ããã¾ãããã
ã¢ãã¤ãã®è¦ç´ ã®é åãä¸ãããããåã®åºéã§ã®é åè¦ç´ ã®æ¼ç®çµæãæ±ããããã®æä½å ¨ä½ã*2ã§è¡ãããã ãåºéåã¯ãæºããã¦ããå¿ è¦ãããã
ã§ã¯æ¬¡ã«ã©ã®ãããªæ¹æ³ã§ãã®æä½ãå®ç¾ããããç´¹ä»ãã¾ãã
ä»çµã¿
åºæ¬çã«two-stack-queueãç¨ãããã¨ã«ãªãã¾ããfrontã¹ã¿ãã¯ã¨backã¹ã¿ãã¯ã¨ãã2ã¤ã®stackãç¨æãã¾ãããããã®ã¹ã¿ãã¯ã¯ã¢ãã¤ãã®ãã¢ãæã¡ã¾ãã
åºéã®å³ç«¯ãé²ããã¨ã
é²ããåã®é
åã®è¦ç´ ããfrontã¹ã¿ãã¯ã«è©°ãè¾¼ã¿ã¾ãããã®ã¨ãããã¢ã®ç¬¬2è¦ç´ ã«ã¯frontã¹ã¿ãã¯ã«å
¥ã£ã¦ããè¦ç´ ã®ç·æ¼ç®çµæãæã£ã¦ããã¾ããããã¯å³ç«¯ãé²ããåã®frontã¹ã¿ãã¯ã®å
é è¦ç´ ã®ç¬¬2è¦ç´ ã«ãæ°ãã«è©°ããè¦ç´ ãæ¼ç®ãããã¨ã§è¨ç®å¯è½ã§ãã
èªç¶æ°ã¨ç©ã«é¢ããã¢ãã¤ãã«é¢ãã¦ä¾ç¤ºããã¨
æ«å°¾âï¸å é |
---|
[(2,2),(3,6)] |
â(5ã追å ) |
[(2,2),(3,6),(5,30)] |
ã®ããã«ãªãã¾ãã
åºéã®å·¦ç«¯ãé²ããã¨ã
backã¹ã¿ãã¯ãã1ã¤è¦ç´ ãpopãã¾ãã
åæ§ã«ä¾ç¤ºããã¨
å é âï¸æ«å°¾ |
---|
[(3,6),(2,2)] |
â(3ãé¤å¤) |
[(2,2)] |
ãã ããbackã¹ã¿ãã¯ã空ã®ã¨ãã¯ãfrontã¹ã¿ãã¯ã®è¦ç´ ã1ã¤ãã¤backã¹ã¿ãã¯ã«ç§»ãããã®å¾backã¹ã¿ãã¯ãã1ã¤è¦ç´ ãpopãã¾ãã移ãéã¯frontã¹ã¿ãã¯ã¨åæ§ã«ããã¢ã®ç¬¬2è¦ç´ ã«ã¯backã¹ã¿ãã¯ã«å
¥ã£ã¦ããè¦ç´ ã®ç·æ¼ç®çµæãæã£ã¦ããã¾ãã
ä¾ç¤ºããã¨
back | front |
---|---|
å é âï¸æ«å°¾ | æ«å°¾âï¸å é |
[] | [(2,2),(3,6)] |
â(3ã移ã) | |
[(3,3)] | [(2,2)] |
â(2ã移ã) | |
[(2,6),(3,3)] | [] |
â(2ãé¤å¤) | |
[(3,3)] | [] |
ã¨ãªãã
æ¼ç®çµæãè¨ç®ããã¨ã
åºéãå®ãçµãã£ãã¨ãã«ãæ¼ç®çµæãè¨ç®ããã«ã¯frontã¨backã®å é è¦ç´ ã®ç¬¬2è¦ç´ å士ãæ¼ç®ããã°è¯ãã§ããä»æ¼ç®ããããã®ã¯frontãªããbackã«å ¥ã£ã¦ãããããããã®å é è¦ç´ ã®ç¬¬2è¦ç´ ã¯ãããããã®ã¹ã¿ãã¯ã«ä»å ¥ã£ã¦ããè¦ç´ ã®ç·æ¼ç®çµæãå ¥ã£ã¦ããããããã®2ã¤ãæ¼ç®ãããã¨ã§ãå ¨ä½ã®ç·æ¼ç®çµæãæ±ãããã¾ãããããã¹ã¿ãã¯ã空ã ã£ãå ´åã¯ãåä½å ã¨ããã°è¯ãã§ãã
è¨ç®é
é åã®åè¦ç´ ã«ã¤ããfrontã«pushãfrontããbackã«ç§»åãbackããpopããè¡ãããªãããããéæãã¦ãã¾ãã
以ä¸ãSWAGã®èª¬æã¨ãªãã¾ããããã§ãããã¾ããï¼ããããªãã£ãã¨æãã®ã§ãåèè³æã®æ¹ãèªã¿ã¾ãããã
ææ¡
ãããããæ¬é¡(ããçµãã)ãªã®ã§ãããä¸ã®æ¹éãæåã«è¦ãã¨ãã«ãçµæ§ç¡é§ããããªãã¨è¨ãã®ã¨ãã¹ã©ã¤ãæå°å¤ã®ã¹ã©ã¤ããã¦ããæãåããè¾ãããªãã¨è¨ãã®ã¨ãæããã®ã§ãèªåãªãã«ã¢ã¬ã³ã¸ãã¦å®è£
ãã¦ã¿ã¾ããã
ã¾ãæåã«ã使ç¨ç¨éãèããã¨ããåºæ¬çã«é
åä¸ãã¹ã©ã¤ãããªããæå°å¤ãæ±ãããã¨è¨ãå½¢ã«ãªããã¨ãå¤ãã¨æãã¾ããããªã®ã§queueã®ãããªæä½ããããæåã«è¿°ã¹ããããªåºéã¯ã¨ãªã®æä½ã¨ãã¦è¦ããæ¹ããããããããã¨æãã¾ããã
ãããªã£ãéã«ãé
åãæã£ã¦ããã¨ãããªãç¡é§ãå¤ãäºã«æ°ä»ãã¾ããã¾ãfrontã¹ã¿ãã¯ã§ãããæ示çã«æã¤å¿
è¦ãç¡ããªãã¾ããå®é使ã£ã¦ããã®ã¯ãfrontã®å
é è¦ç´ ã®ç¬¬2è¦ç´ ã ãã§ãããã¨ããããã¾ããé
åãå¥ã«æã£ã¦ãããããindexã ãè¦ãã¦ããã°ãå¾ã
backã¹ã¿ãã¯ã«çªã£è¾¼ãã¨ãã«ãå°ãã¾ããããã£ã¦å®éã«æã¤å¿
è¦ãããã®ã¯ãfrontã¹ã¿ãã¯ã®ç·æ¼ç®çµæã®ã¿ã¨ãªãã¾ãã
ã¾ãbackã¹ã¿ãã¯ã§ããã使ãã®ã¯æ¼ç®çµæã®ã¿ã§ããã®ã§ãããããã®è¦ç´ ãè¦ãã¦ããå¿
è¦ã¯å
¨ãããã¾ããããã£ã¦è©°ãè¾¼ãã®ã¯æ¼ç®çµæã®ã¿ã¨ãããã¨ãã§ãã¾ãã
以ä¸ãè¸ã¾ãã¦å®è£
ãããã®ãã以ä¸ã¨ãªãã¾ãã
template <class Monoid,Monoid e> struct SWAG{ std::function<Monoid(Monoid,Monoid)> op; std::vector<Monoid> v; Monoid front; std::stack<Monoid> back; size_t l,r; explicit SWAG(std::function<Monoid(Monoid,Monoid)> op) :op(std::move(op)),v(),front(e),back(),l(0),r(0){}; SWAG(std::function<Monoid(Monoid,Monoid)> op,std::vector<Monoid>&v_) :op(std::move(op)),v(v_.size()),front(e),back(),l(0),r(0){ std::copy(v_.begin(),v_.end(),v.begin()); }; Monoid fold(size_t i,size_t j){ while(r<j) front=op(front,v[r++]); while(l<i){ if(back.empty()){ Monoid tmp{e}; for(size_t u=r;u-->l;) back.emplace(tmp=op(v[u],tmp)); front=e; } back.pop(); ++l; } if(back.empty()) return front; return op(back.top(),front); } };
ãã¡ããã¡ããã¦ãã¾ãããå¯èªæ§ãã ãã¶ä½ãå®è£ ããã¦ãã¾ãããfoldé¢æ°ã®ã¨ããã ãã¿ã¦ãããã°å¤§ä½ãããã¨æãã¾ãã話ããããã¨ã¯ä»¥ä¸ã¨ãªãã¾ãã
使ç¨ä¾
æåºã³ã¼ã
#include <iostream> #include <functional> #include <vector> #include <stack> //SWAGã¯çç¥ template<class T> T gcd(T n,T m){ while(m){ n%=m; std::swap(n,m); } return n; } template<class T> T lcm(T n,T m){ T c=n*m/gcd(n,m); if(c>1000000001) c=1000000001; return c; } int main(){ using ll = long long; int n; ll x; std::cin>>n>>x; std::vector<ll> a(n); for(auto&i:a) std::cin>>i; std::function<ll(ll,ll)> op=[](ll i,ll j){return lcm(i,j);}; SWAG<ll,1> sw(op,a); int r=0,ans=0,ansl=0; for(int l=0;l<n;++l){ while(r<n&&sw.fold(l,r+1)<x) ++r; if(ans<r-l){ ans=r-l; ansl=l; } } std::cout<<ansl+1<<" "<<ansl+ans<<std::endl; }
Segment TreeãSparse Tableã§å®è£ ããã¨ããã¾ãå®è£ ããªãã¨ã¨ãªãã軽ãã®å®è£ ãããªãã¨éãã¾ããããSWAGã ã¨ã¨ãªããéã«å®è£ ãã¦ãéããã¨ãã§ãã¾ãã
ãããã«
ãã¼ã¿æ§é ã®è¨äºãæ¸ãã®ã¯é£ããã¨è¨ããã¨ãçãã»ã©ãããã¾ããã軽ãæ°æã¡ã§èª¬æãªãã¦æ¸ããããããªãã§ãããããè¨ãã®ã¯ä¸æã人ã«ä»»ãããâ¦()ãããã§ã¯ãã¾ãä¼ãæ¥ã¾ã§ã
åèè³æ
スライド最小値を半群に一般化する - noshi91のメモ
ç¨æããã«ã¯ãã¤ããä¸è©±ã«ãªã£ã¦ãã¾ãããããã¨ããããã¾ãã